PHP实现深度优先搜索算法(DFS,Depth First Search)详解

本文实例讲述了PHP实现深度优先搜索算法。分享给大家供大家参考，具体如下：深度优先搜

本文实例讲述了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 深度优先搜索 算法 DFS Depth First Search