1、圖的深度優先遍歷類似前序遍歷,圖的廣度優先類似樹的層序遍歷
2、將圖進行變形,根據頂點和邊的關系進行層次劃分,使用隊列來進行遍歷
3、廣度優先遍歷的關鍵點是使用一個隊列來把當前結點的所有下一級關聯點存進去,依次進行

鄰接矩陣的廣度優先遍歷:

BFS(G)
for i=0;i<G->numVertexes;i++
visited[i]=false;//檢測是否訪問過
for i=0;i<G.numVertexes;i++//遍歷頂點
if visited[i]==true break;//訪問過的斷掉
visited[i]=true //當前頂點訪問
InQueue(i)      //當前頂點入隊列
while(!QueueEmpty()) //當前隊列不為空
i=OutQueue() //隊列元素出隊列
for j=0;j<G->numVertexes;j++ //遍歷頂點
if G->arc[i][j]==1 && !visited[j] //當前頂點與其他頂點存在關系并且未被訪問
visited[j]=true //標記此頂點
InQueue(j)      //此頂點入隊列,會排在后面等前面一層的全遍歷完才會遍歷這個

深度優先遍歷DFS:

DFSTravserse G
    for i=0;i<G.xNum;i++
        if !visted[i]
            DFS(G,i)
DFS G,i
    visted[i]=true
    print G.vexs[i]
    if G.arc[i][j]==1 && !visited[j]
        DFS(G,j)

圖的物理存儲的實現:

鄰接矩陣 鄰接鏈表 十字鏈表 鄰接多重表

有向圖的存儲方法:十字鏈表

無向圖存儲的優化:鄰接多重表

圖的遍歷:

1、從圖中某一頂點出發訪遍圖中其余頂點,且使每個頂點僅被訪問一次
2、需要給訪問過的頂點打上標記,設置個數組visited[n],訪問過后設置為1
3、遍歷次序:深度優先遍歷和廣度優先遍歷

深度優先遍歷DFS:

1、類似走迷宮右手定則,走一個做標記,一直往右走,直到重復了,就退回上一個頂點
2、從某個頂點v出發訪問和v有路徑相通的頂點,遞歸調用

<?php
class Graph{
        public $vertexs;
        public $arc;
        public $num=5;
}
$G=new Graph();
for($i=0;$i<$G->num;$i++){
        $G->vertexs[$i]="V{$i}";
}
$G->arc[1][0]=9;
$G->arc[1][2]=3;
$G->arc[2][0]=2;
$G->arc[2][3]=5;
$G->arc[3][4]=1;
$G->arc[0][4]=6;
//廣度優先遍歷
function BFS($G){
        $res=array();
        $queue=array();
        for($i=0;$i<$G->num;$i++){
                $visited[$i]=false;
        }   
        for($i=0;$i<$G->num;$i++){
                if($visited[$i]){
                        break;
                }   
                $visited[$i]=true;
                $res[]=$G->vertexs[$i];
                array_push($queue,$i);
                while(!empty($queue)){
                        $v=array_pop($queue);
                        for($j=0;$j<$G->num;$j++){
                                if($G->arc[$v][$j]>0 && !$visited[$j]){
                                        $visited[$j]=true;
                                        $res[]=$G->vertexs[$j];
                                        array_push($queue,$j);
                                }   
                        }   
                }   
        }   
        return $res;
}
//深度優先遍歷
function DFS($G,$i){
        static $res;
        static $visited;
        if(!$visited[$i]){
                $visited[$i]=true;
                $res[]=$G->vertexs[$i];
        }
                for($j=0;$j<$G->num;$j++){
                        if($G->arc[$i][$j]>0 && !$visited[$j]){
                                $visited[$j]=true;
                                $res[]=$G->vertexs[$j];
                                DFS($G,$j);
                        }
                }
        return $res;
}
$b=BFS($G);
$d=DFS($G,1);
var_dump($b);
var_dump($d);

array(5) {
  [0]=>
  string(2) "V0"
  [1]=>
  string(2) "V4"
  [2]=>
  string(2) "V1"
  [3]=>
  string(2) "V2"
  [4]=>
  string(2) "V3"
}
array(5) {
  [0]=>
  string(2) "V1"
  [1]=>
  string(2) "V0"
  [2]=>
  string(2) "V4"
  [3]=>
  string(2) "V2"
  [4]=>
  string(2) "V3"
}

以上就是php如何實現鄰接矩陣圖的廣度和深度優先遍歷（代碼）的詳細內容，更多請關注php中文網其它相關文章！