时间:2021-07-01 10:21:17 帮助过:4人阅读
本文实例讲述了PHP实现深度优先搜索算法。分享给大家供大家参考,具体如下:
深度优先搜索的实现原理:
实现代码:
- <?php
- class Search_Method
- {
- //无向图的数组描述
- private $dfs_save;
- //全局记录数组
- private $arr;
- //控制分支-
- private $k = 0;
- public function __construct()
- {
- $this->dfs_save = array(
- array(0,1,1,1,0,0,0,0,0),
- array(1,0,0,0,1,0,0,0,0),
- array(1,0,0,0,0,1,0,0,0),
- array(1,0,0,0,0,0,1,0,0),
- array(0,1,0,0,0,1,0,0,1),
- array(0,0,1,0,1,0,0,1,0),
- array(0,0,0,1,0,0,0,0,0),
- array(0,0,0,0,0,1,0,0,0),
- array(0,0,0,0,1,0,0,0,0),
- );
- $this->arr = array();
- }
- //深度优先搜索的递归实现方法
- public function dfs($v)
- {
- //对顶点做一些操作
- echo str_repeat("-",$this->k);
- echo 'V'.($v+1).'<br>';
- //记录已访问的顶点
- $this->arr[]= $v;
- //查找与顶点相连接的顶点,如果存在就继续深度优先搜索
- for($i=0;$i<9;$i++)
- {
- if(!in_array($i,$this->arr)&&$this->dfs_save[$v][$i]==1)
- {
- $this->k++;
- $this->dfs($i);
- }
- }
- $this->k--;
- return;
- }
- }
- ?>
实现输出结果:
- V1
- -V2
- --V5
- ---V6
- ----V3
- ----V8
- ---V9
- -V4
- --V7
以上就是详解PHP实现深度优先搜索算法的详细内容,更多请关注Gxl网其它相关文章!