.png)
相關(guān)關(guān)鍵詞
關(guān)于我們
最新文章
PHP實現(xiàn)深度優(yōu)先搜索算法(DFS,Depth First Search)詳解
本文實例講述了PHP實現(xiàn)深度優(yōu)先搜索算法。分享給大家供大家參考，具體如下：
深度優(yōu)先搜索的實現(xiàn)原理：
實現(xiàn)代碼：
<?php
class Search_Method
{
//無向圖的數(shù)組描述
private $dfs_save;
//全局記錄數(shù)組
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();
}
//深度優(yōu)先搜索的遞歸實現(xiàn)方法
public function dfs($v)
{
//對頂點做一些操作
echo str_repeat("-",$this->k);
echo 'V'.($v+1).'<br>';
//記錄已訪問的頂點
$this->arr[]= $v;
//查找與頂點相連接的頂點，如果存在就繼續(xù)深度優(yōu)先搜索
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;
}
}
?>