PHP實現深度優先搜索算法(DFS,Depth First Search)詳解

更新:2017-10-25    編輯:凌藍    來源:geguai    人氣:加載中...    字號:|

標簽:實現  搜索  詳解  算法  search  深度  百度搜索

本文實例講述了PHP實現深度優先搜索算法分享給大家供大家參考,具體如下:

深度優先搜索實現原理:

PHP實現深度優先搜索算法(DFS,Depth First Search)詳解

實現代碼:

<?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


評論列表(網友評論僅供網友表達個人看法,并不表明本站同意其觀點或證實其描述)

站點導航

您可能在找這些
黑龙江快乐十分走势图