4、教你通透徹底理解：BFS和DFS優(yōu)先搜索算法

?

?作者：July??二零一一年一月一日

---------------------------------

本人參考：算法導(dǎo)論?
本人聲明：個(gè)人原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處。

ok，開始。

翻遍網(wǎng)上，關(guān)于此類BFS和DFS算法的文章，很多。但，都說不出個(gè)所以然來。
讀完此文，我想，
你對(duì)圖的廣度優(yōu)先搜索和深度優(yōu)先搜索定會(huì)有個(gè)通通透透，徹徹底底的認(rèn)識(shí)。

---------------------

咱們由BFS開始：
首先，看下算法導(dǎo)論一書關(guān)于 此BFS 廣度優(yōu)先搜索算法的概述。
算法導(dǎo)論第二版，中譯本，第324頁。
廣度優(yōu)先搜索（BFS）
在Prime最小生成樹算法，和Dijkstra單源最短路徑算法中，都采用了與BFS 算法類似的思想。

//u 為 v 的先輩或父母。
BFS(G, s) 1 for each vertex u ∈ V [G] - {s}2 do color[u] ← WHITE3 d[u] ← ∞4 π[u] ← NIL//除了源頂點(diǎn)s之外，第1-4行置每個(gè)頂點(diǎn)為白色，置每個(gè)頂點(diǎn)u的d[u]為無窮大，//置每個(gè)頂點(diǎn)的父母為NIL。 5 color[s] ← GRAY//第5行，將源頂點(diǎn)s置為灰色，這是因?yàn)樵谶^程開始時(shí)，源頂點(diǎn)已被發(fā)現(xiàn)。 6 d[s] ← 0 //將d[s]初始化為0。 7 π[s] ← NIL //將源頂點(diǎn)的父頂點(diǎn)置為NIL。 8 Q ← ?9 ENQUEUE(Q, s) //入隊(duì)//第8、9行，初始化隊(duì)列Q，使其僅含源頂點(diǎn)s。 10 while Q ≠ ? 11 do u ← DEQUEUE(Q) //出隊(duì)//第11行，確定隊(duì)列頭部Q頭部的灰色頂點(diǎn)u，并將其從Q中去掉。 12 for each v ∈ Adj[u] //for循環(huán)考察u的鄰接表中的每個(gè)頂點(diǎn)v 13 do if color[v] = WHITE 14 then color[v] ← GRAY //置為灰色 15 d[v] ← d[u] + 1 //距離被置為d[u]+1 16 π[v] ← u //u記為該頂點(diǎn)的父母 17 ENQUEUE(Q, v) //插入隊(duì)列中 18 color[u] ← BLACK //u 置為黑色

由下圖及鏈接的演示過程，清晰在目，也就不用多說了：?

廣度優(yōu)先遍歷演示地址： http://sjjg.js.zwu.edu.cn/SFXX/sf1/gdyxbl.html -----------------------------------------------------------------------------------------------------------------
ok，不再贅述。接下來，具體講解深度優(yōu)先搜索算法。
深度優(yōu)先探索算法 DFS?
//u 為 v 的先輩或父母。
DFS(G) 1 for each vertex u ∈ V [G] 2 do color[u] ← WHITE 3 π[u] ← NIL //第1-3行，把所有頂點(diǎn)置為白色，所有π 域被初始化為NIL。 4 time ← 0 //復(fù)位時(shí)間計(jì)數(shù)器 5 for each vertex u ∈ V [G] 6 do if color[u] = WHITE 7 then DFS-VISIT(u) //調(diào)用DFS-VISIT訪問u，u成為深度優(yōu)先森林中一棵新的樹//第5-7行，依次檢索V中的頂點(diǎn)，發(fā)現(xiàn)白色頂點(diǎn)時(shí)，調(diào)用DFS-VISIT訪問該頂點(diǎn)。//每個(gè)頂點(diǎn)u 都對(duì)應(yīng)于一個(gè)發(fā)現(xiàn)時(shí)刻d[u]和一個(gè)完成時(shí)刻f[u]。 DFS-VISIT(u) 1 color[u] ← GRAY //u 開始時(shí)被發(fā)現(xiàn)，置為白色 2 time ← time +1 //time 遞增 3 d[u] <-time //記錄u被發(fā)現(xiàn)的時(shí)間 4 for each v ∈ Adj[u] //檢查并訪問 u 的每一個(gè)鄰接點(diǎn) v 5 do if color[v] = WHITE //如果v 為白色，則遞歸訪問v。 6 then π[v] ← u //置u為 v的先輩 7 DFS-VISIT(v) //遞歸深度，訪問鄰結(jié)點(diǎn)v 8 color[u] <-BLACK //u 置為黑色，表示u及其鄰接點(diǎn)都已訪問完成 9 f [u] ? time ← time +1 //訪問完成時(shí)間記錄在f[u]中。 //完 第1-3行，5-7行循環(huán)占用時(shí)間為O（V），此不包括調(diào)用DFS-VISIT的時(shí)間。
??? 對(duì)于每個(gè)頂點(diǎn)v(-V，過程DFS-VISIT僅被調(diào)用依次，因?yàn)橹挥袑?duì)白色頂點(diǎn)才會(huì)調(diào)用此過程。
第4-7行，執(zhí)行時(shí)間為O（E）。
因此，總的執(zhí)行時(shí)間為O(V+E)。
?
下面的鏈接，給出了深度優(yōu)先搜索的演示系統(tǒng)：

圖的深度優(yōu)先遍歷演示系統(tǒng)：

http://sjjg.js.zwu.edu.cn/SFXX/sf1/sdyxbl.html

?

===============

最后，咱們?cè)賮砜瓷疃葍?yōu)先搜索的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)
1、DFS 遞歸實(shí)現(xiàn)：

void dftR(PGraphMatrix inGraph) {PVexType v; assertF(inGraph!=NULL,"in dftR, pass in inGraph is null/n");printf("/n===start of dft recursive version===/n");for(v=firstVertex(inGraph);v!=NULL;v=nextVertex(inGraph,v))if(v->marked==0)dfsR(inGraph,v);printf("/n===end of dft recursive version===/n"); } void dfsR(PGraphMatrix inGraph,PVexType inV) {PVexType v1;assertF(inGraph!=NULL,"in dfsR,inGraph is null/n");assertF(inV!=NULL,"in dfsR,inV is null/n");inV->marked=1;visit(inV);for(v1=firstAdjacent(inGraph,inV);v1!=NULL;v1=nextAdjacent(inGraph,inV,v1))//v1當(dāng)為v的鄰接點(diǎn)。 if(v1->marked==0)dfsR(inGraph,v1); }

2、DFS 非遞歸實(shí)現(xiàn)
非遞歸版本---借助結(jié)點(diǎn)類型為隊(duì)列的棧實(shí)現(xiàn)
?? 聯(lián)系樹的前序遍歷的非遞歸實(shí)現(xiàn)：
?? 可知，其中無非是分成“探左”和“訪右”兩大塊訪右需借助棧中彈出的結(jié)點(diǎn)進(jìn)行.
?? 在圖的深度優(yōu)先搜索中，同樣可分成“深度探索”和“回訪上層未訪結(jié)點(diǎn)”兩塊:
??? 1、圖的深度探索這樣一個(gè)過程和樹的“探左”完全一致,
只要對(duì)已訪問過的結(jié)點(diǎn)作一個(gè)判定即可。
??? 2、而圖的回訪上層未訪結(jié)點(diǎn)和樹的前序遍歷中的“訪右”也是一致的.
但是，對(duì)于樹而言，是提供rightSibling這樣的操作的，因而訪右相當(dāng)好實(shí)現(xiàn)。

在這里，若要實(shí)現(xiàn)相應(yīng)的功能，考慮將每一個(gè)當(dāng)前結(jié)點(diǎn)的下層結(jié)點(diǎn)中，如果有m個(gè)未訪問結(jié)點(diǎn),
則最左的一個(gè)需要訪問，而將剩余的m-1個(gè)結(jié)點(diǎn)按從左到右的順序推入一個(gè)隊(duì)列中。
并將這個(gè)隊(duì)列壓入一個(gè)堆棧中。

?? 這樣，當(dāng)當(dāng)前的結(jié)點(diǎn)的鄰接點(diǎn)均已訪問或無鄰接點(diǎn)需要回訪時(shí)，
則從棧頂?shù)年?duì)列結(jié)點(diǎn)中彈出隊(duì)列元素，將隊(duì)列中的結(jié)點(diǎn)元素依次出隊(duì),
若已訪問，則繼續(xù)出隊(duì)(當(dāng)當(dāng)前隊(duì)列結(jié)點(diǎn)已空時(shí)，則繼續(xù)出棧，彈出下一個(gè)棧頂?shù)年?duì)列)，
直至遇到有未訪問結(jié)點(diǎn)(訪問并置當(dāng)前點(diǎn)為該點(diǎn))或直到棧為空（則當(dāng)前的深度優(yōu)先搜索樹停止搜索）。

?

將算法通過精簡(jiǎn)過的C源程序的方式描述如下:

//dfsUR:功能從一個(gè)樹的某個(gè)結(jié)點(diǎn)inV發(fā)，以深度優(yōu)先的原則訪問所有與它相鄰的結(jié)點(diǎn) void dfsUR(PGraphMatrix inGraph,PVexType inV) {PSingleRearSeqQueue tmpQ; //定義臨時(shí)隊(duì)列，用以接受棧頂隊(duì)列及壓棧時(shí)使用 PSeqStack testStack; //存放當(dāng)前層中的m-1個(gè)未訪問結(jié)點(diǎn)構(gòu)成隊(duì)列的堆棧.//一些變量聲明,初始化動(dòng)作//訪問當(dāng)前結(jié)點(diǎn) inV->marked=1; //當(dāng)marked值為1時(shí)將不必再訪問。 visit(inV);do{flag2=0;//flag2是一個(gè)重要的標(biāo)志變量，用以、說明當(dāng)前結(jié)點(diǎn)的所有未訪問結(jié)點(diǎn)的個(gè)數(shù),兩個(gè)以上的用2代表//flag2:0:current node has no adjacent which has not been visited.//1:current node has only one adjacent node which has not been visited.//2:current node has more than one adjacent node which have not been visited. v1=firstAdjacent(inGraph,inV); //鄰接點(diǎn)v1 while(v1!=NULL) //訪問當(dāng)前結(jié)點(diǎn)的所有鄰接點(diǎn) {if(v1->marked==0) //.. { if(flag2==0) //當(dāng)前結(jié)點(diǎn)的鄰接點(diǎn)有0個(gè)未訪問 {//首先，訪問最左結(jié)點(diǎn) visit(v1);v1->marked=1; //訪問完成 flag2=1; ////記錄最左兒子 lChildV=v1; //save the current node's first unvisited(has been visited at this time)adjacent node } else if(flag2==1) //當(dāng)前結(jié)點(diǎn)的鄰接點(diǎn)有1個(gè)未訪問 {//新建一個(gè)隊(duì)列，申請(qǐng)空間，并加入第一個(gè)結(jié)點(diǎn) flag2=2;}else if(flag2==2)//當(dāng)前結(jié)點(diǎn)的鄰接點(diǎn)有2個(gè)未被訪問 {enQueue(tmpQ,v1);}}v1=nextAdjacent(inGraph,inV,v1);}if(flag2==2)//push adjacent nodes which are not visited. { //將存有當(dāng)前結(jié)點(diǎn)的m-1個(gè)未訪問鄰接點(diǎn)的隊(duì)列壓棧 seqPush(testStack,tmpQ);inV=lChildV;}else if(flag2==1)//only has one adjacent which has been visited. { //只有一個(gè)最左兒子，則置當(dāng)前點(diǎn)為最左兒子 inV=lChildV;}else if(flag2==0)//has no adjacent nodes or all adjacent nodes has been visited { //當(dāng)當(dāng)前的結(jié)點(diǎn)的鄰接點(diǎn)均已訪問或無鄰接點(diǎn)需要回訪時(shí)，則從棧頂?shù)年?duì)列結(jié)點(diǎn)中彈出隊(duì)列元素，//將隊(duì)列中的結(jié)點(diǎn)元素依次出隊(duì),若已訪問，則繼續(xù)出隊(duì)(當(dāng)當(dāng)前隊(duì)列結(jié)點(diǎn)已空時(shí)，//則繼續(xù)出棧，彈出下一個(gè)棧頂?shù)年?duì)列)，直至遇到有未訪問結(jié)點(diǎn)(訪問并置當(dāng)前點(diǎn)為該點(diǎn))或直到棧為空。 flag=0;while(!isNullSeqStack(testStack)&&!flag){ v1=frontQueueInSt(testStack); //返回棧頂結(jié)點(diǎn)的隊(duì)列中的隊(duì)首元素 deQueueInSt(testStack); //將棧頂結(jié)點(diǎn)的隊(duì)列中的隊(duì)首元素彈出 if(v1->marked==0){ visit(v1);v1->marked=1;inV=v1;flag=1; }}} }while(!isNullSeqStack(testStack));//the algorithm ends when the stack is null }

-----------------------------

上述程序的幾點(diǎn)說明：

所以，這里應(yīng)使用的數(shù)據(jù)結(jié)構(gòu)的構(gòu)成方式應(yīng)該采用下面這種形式:
1)隊(duì)列的實(shí)現(xiàn)中，每個(gè)隊(duì)列結(jié)點(diǎn)均為圖中的結(jié)點(diǎn)指針類型.
定義一個(gè)以隊(duì)列尾部下標(biāo)加隊(duì)列長(zhǎng)度的環(huán)形隊(duì)列如下:

struct SingleRearSeqQueue; typedef PVexType QElemType; typedef struct SingleRearSeqQueue* PSingleRearSeqQueue; struct SingleRearSeqQueue {int rear;int quelen;QElemType dataPool[MAXNUM]; };

其余基本操作不再贅述.????

2)堆棧的實(shí)現(xiàn)中，每個(gè)堆棧中的結(jié)點(diǎn)元素均為一個(gè)指向隊(duì)列的指針,定義如下:

#define SEQ_STACK_LEN 1000 #define StackElemType PSingleRearSeqQueue struct SeqStack; typedef struct SeqStack* PSeqStack; struct SeqStack {StackElemType dataArea[SEQ_STACK_LEN];int slot; };

為了提供更好的封裝性，對(duì)這個(gè)堆棧實(shí)現(xiàn)兩種特殊的操作

2.1) deQueueInSt操作用于將棧頂結(jié)點(diǎn)的隊(duì)列中的隊(duì)首元素彈出.

void deQueueInSt(PSeqStack inStack) {if(isEmptyQueue(seqTop(inStack))||isNullSeqStack(inStack)){printf("in deQueueInSt,under flow!/n");return; } deQueue(seqTop(inStack));if(isEmptyQueue(seqTop(inStack)))inStack->slot--; }

2.2) frontQueueInSt操作用以返回棧頂結(jié)點(diǎn)的隊(duì)列中的隊(duì)首元素.

QElemType frontQueueInSt(PSeqStack inStack) {if(isEmptyQueue(seqTop(inStack))||isNullSeqStack(inStack)){printf("in frontQueueInSt,under flow!/n");return '/r'; } return getHeadData(seqTop(inStack)); }

?

===================

ok，本文完。

總結(jié)

以上是生活随笔為你收集整理的BFS和DFS优先搜索算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。