廣度優先搜索遍歷演算法的圖解

Ⅰ 基本演算法——深度優先搜索（DFS）和廣度優先搜索（BFS）

        深度優先搜索和廣度優先搜索，都是圖形搜索演算法，它兩相似，又卻不同，在應用上也被用到不同的地方。這里拿一起討論，方便比較。

一、深度優先搜索

        深度優先搜索屬於圖演算法的一種，是一個針對圖和樹的遍歷演算法，英文縮寫為DFS即Depth First Search。深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

基本步奏

（1）對於下面的樹而言，DFS方法首先從根節點1開始，其搜索節點順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優先選擇左分枝）。

（2）從stack中訪問棧頂的點；

（3）找出與此點鄰接的且尚未遍歷的點，進行標記，然後放入stack中，依次進行；

（4）如果此點沒有尚未遍歷的鄰接點，則將此點從stack中彈出，再按照（3）依次進行；

（5）直到遍歷完整個樹，stack里的元素都將彈出，最後棧為空，DFS遍歷完成。

二、廣度優先搜索

        廣度優先搜索（也稱寬度優先搜索，縮寫BFS，以下採用廣度來描述）是連通圖的一種遍歷演算法這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。基本過程，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。一般用隊列數據結構來輔助實現BFS演算法。

基本步奏

（1）給出一連通圖，如圖，初始化全是白色（未訪問）；

（2）搜索起點V1（灰色）；

（3）已搜索V1（黑色），即將搜索V2，V3，V4（標灰）；

（4）對V2，V3，V4重復以上操作；

（5）直到終點V7被染灰，終止；

（6）最短路徑為V1，V4，V7.

Ⅱ 廣度優先演算法作法

在圖的搜索策略中，BFS（廣度優先搜索）採用了一種系統性的方法，目標是遍歷圖中的每一個節點，以期找到預期的結果，它不依賴於結果可能的位置，而是全面地探索整個圖直至找到答案。不同於某些依賴經驗法則的演算法，BFS採取了更為直接的搜索方式。

從演算法的角度看，每個新發現的節點會通過先進先出的原則加入到一個叫做open的隊列中，這個隊列通常用於存儲尚未被考察的節點。與此同時，那些已經被訪問過的節點會被放入一個稱為closed的集合中，以避免重復搜索。（open-closed數據結構的運用）

搜索演算法實際上是根據初始條件和擴展規則構造一顆「解答樹」並尋找符合目標狀態的節點的過程。所有的搜索演算法從最終的演算法實現上來看，都可以劃分成兩個部分——控制結構（擴展節點的方式）和產生系統（擴展節點），而所有的演算法優化和改進主要都是通過修改其控制結構來完成的。其實，在這樣的思考過程中，我們已經不知不覺地將一個具體的問題抽象成了一個圖論的模型——樹，即搜索演算法的使用第一步在於搜索樹的建立。

Ⅲ 圖遍歷的演算法

圖的遍歷方法目前有深度優先搜索法和廣度（寬度）優先搜索法兩種演算法。 深度優先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //訪問標志數組初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //對尚未訪問的頂點調用DFS
}
void DFS(Graph G, int v){ //從第v個頂點出發遞歸地深度優先遍歷圖G
visited[v]=TRUE; VisitFunc(v); //訪問第v個頂點
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空（0）。
//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
//若w是v的最後一個鄰接點，則返回空（0）。
if(!visited[w])
DFS(G, w); //對v的尚未訪問的鄰接頂點w調用DFS
} 圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…, vi t，並均標記已訪問過，然後再按照vi1,vi2,…, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空輔助隊列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入隊列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //隊頭元素出隊並置為u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}

Ⅳ 深度優先搜索遍歷和廣度優先搜索的遍歷序列及具體步驟和原因，

1->2->3->4 （表示1可達到2，達到3，達到4）

2->1->3->5

3->1->2->4->5->6

4->1->3->6

5->2->3->6

6->3->4->5

廣度優先搜索就是把每一行按照順序輸出，去掉重復的，即先看1，有1,2,3,4，然後看2，因為有3,4了，所以只要5，然後看3，以此類推。。一行行來。

深度優先搜索，是先看1，然後1可以到2，然後直接看2,2可以到3,5隨便選一個都可以，我們到3好了，然後看3的那行可以到1,2,4,5,6隨便選一個都可以，不過要去掉重復的，以此類推。可以排出很多種的。

(4)廣度優先搜索遍歷演算法的圖解擴展閱讀：

假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點(源點)，則深度優先遍歷可定義如下：首先訪問出發點v，並將其標記為已訪問過；然後依次從v出發搜索v的每個鄰接點w。

若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。

圖的深度優先遍歷類似於樹的前序遍歷。採用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優先搜索(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。

Ⅳ 已知一個有向圖如圖，請分別寫出從頂點a出發進行深度優先遍歷和廣度優先遍歷所得到的頂點序列及生成樹。

一、深度生成樹：abdcefigh，如下圖所示：

相關特點：

（1）生成樹協議提供一種控制環路的方法。採用這種方法，在連接發生問題的時候，你控制的乙太網能夠繞過出現故障的連接。

（2）生成樹中的根橋是一個邏輯的中心，並且監視整個網路的通信。最好不要依靠設備的自動選擇去挑選哪一個網橋會成為根橋。

（3）生成樹協議重新計算是繁冗的。恰當地設置主機連接埠(這樣就不會引起重新計算)，推薦使用快速生成樹協議。

（4）生成樹協議可以有效的抑制廣播風暴。開啟生成樹協議後抑制廣播風暴，網路將會更加穩定，可靠性、安全性會大大增強。

Ⅵ 無向有權的圖的深度、廣度優先遍歷怎麼做的啊，他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1） 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。

2） 深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然後遍歷其左子樹，最後遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然後訪問根，最後遍歷其右子樹。
後序遍歷：對任一子樹，先遍歷其左子樹，然後遍歷其右子樹，最後訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

3）深度優先搜素演算法：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。

廣度優先搜索演算法：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。