深度和廣度優先搜尋

1、深度優先搜尋的過程

（1）從圖中某個頂點v出發，通路v.

（2）找出剛通路過的頂點的第一個未被通路的鄰接點，通路該鄰接點。然後再以該節點為新節點，重複此步驟，直到剛通路過的頂點沒有未被通路的鄰接頂點為止。

（3）傳回前一個通路過的頂點沒有被通路過的鄰接頂點，找出該頂點的下一個未被通路的鄰接點，通路該節點。（因為一個節點會有多個鄰接點，先通路一個鄰接點，通路結束後再傳回來到該節點，去通路另一個鄰接點）。

（4）重複上面的步驟（2）（3），直到所有的節點都被通路結束。

2廣度優先搜尋的過程

（1）從圖中某個頂點v出發，通路v。

（2）依次通路v的各個未曾通路過的鄰接點。

（3）分别從這些鄰接點出發依次通路他們的鄰接點。

下面舉個例子

深度優先：

根據上面的圖：從頂點v1出發，通路第一個鄰接點v2，然後再通路v2的第一個鄰接點v4，再通路v4的第一個鄰接點v8，v8的第一個鄰接點v5，然後發現v5的鄰接點都已經被通路，然後一直退回來，再去通路v1的第二個鄰接點v3，然後通路v3的第一個 鄰接點v6，然後通路v6的第一個鄰接點v7，發現v7的所有鄰接點都已經被通路，一直退回來到v1，然後v1的所有鄰接點都被通路完了，通路結束。

v1—>v2—>v4—>v8—>v5—>v3—>v6—>v6—>v7.

下面是代碼（c語言,書上的代碼）：

bool visited[MVNum];
void DFS(Graph,G,int v){
      cout<<v;visited[v]=true;
      for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){
         if(!visited[w]) DFS(G,w);
         }
         }
           

廣度優先

根據上面的圖：

（1）從頂點v1出發，通路v1的鄰接點v2，v3。

（2）然後先通路第一個鄰接點v2的鄰接點v4，v5。

（3）再去通路v3的鄰接點v6，v7。

（4）再去通路v4的鄰接點v8.

（5）所有的點都别通路完了，通路結束。

v1—>v2—>v3—>v4—>v5—>v6—>v7---->v8。