深度優(yōu)先搜索算法DFS

1、深度優(yōu)先搜索算法DFS= = = 1.首先選定圖的類別（有向圖、無(wú)向圖），再選定圖的存儲(chǔ)結(jié)構(gòu)，根據(jù)輸入的頂點(diǎn)或者邊建立圖；并把相應(yīng)的鄰接表或者鄰接矩陣輸出； 2.根據(jù)已有的鄰接矩陣或鄰接表用遞歸方法編寫深度優(yōu)先搜索遍歷算法，并輸出遍歷結(jié)果；  dfs.rar - 深度優(yōu)先搜索算法解決八碼難題 Draw1Doc.rar - 簡(jiǎn)單的繪圖程序,能畫(huà)點(diǎn),直線,多邊形等,比較簡(jiǎn)單= = = =這里的圖的深度優(yōu)先算法利用了棧來(lái)實(shí)現(xiàn)。 圖的深度遍歷原則： 1 如果有可能，訪問(wèn)一個(gè)領(lǐng)接的未訪問(wèn)的節(jié)點(diǎn)，標(biāo)記它，并把它放入棧中。 2 當(dāng)不能執(zhí)行規(guī)則 1 時(shí)，如果棧不為空，則從棧中彈出一個(gè)元素。

2、 3 如果不能執(zhí)行規(guī)則 1 和規(guī)則 2 時(shí)，則完成了遍歷。 代碼中的圖使用的是Graph 圖鄰接矩陣法 來(lái)表示，其他的表示法請(qǐng)見(jiàn)：Graph 圖鄰接表法 代碼中的Stack為輔助結(jié)構(gòu)，用來(lái)記載訪問(wèn)過(guò)的節(jié)點(diǎn)。棧的詳細(xì)描述可以見(jiàn)：ArrayStack 棧 ，LinkedStack 棧 。 Vertex表示圖中的節(jié)點(diǎn)，其中包含訪問(wèn)，是否訪問(wèn)，清除訪問(wèn)標(biāo)志的方法。 Graph.main：提供簡(jiǎn)單測(cè)試。代碼可以以指定下標(biāo)的節(jié)點(diǎn)開(kāi)始作深度遍歷。 代碼比較簡(jiǎn)單，除了Graph.dsf(int i)深度優(yōu)先遍歷算法外沒(méi)有過(guò)多注釋。= = = =深度優(yōu)先搜索 DFS正如算法名稱那樣，深度優(yōu)先搜索所遵循的搜索策略

3、是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對(duì)于最新發(fā)現(xiàn)的頂點(diǎn)，如果它還有以此為起點(diǎn)而未探測(cè)到的邊，就沿此邊繼續(xù)漢下去。當(dāng)結(jié)點(diǎn)v的所有邊都己被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v有那條邊的始結(jié)點(diǎn)。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的結(jié)點(diǎn)，則選擇其中一個(gè)作為源結(jié)點(diǎn)并重復(fù)以上過(guò)程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。和寬度優(yōu)先搜索類似，每當(dāng)掃描已發(fā)現(xiàn)結(jié)點(diǎn)u的鄰接表從而發(fā)現(xiàn)新結(jié)點(diǎn)v時(shí)，深度優(yōu)先搜索將置v的先輩域v為u。和寬度優(yōu)先搜索不同的是，前者的先輩子圖形成一棵樹(shù)，而后者產(chǎn)生的先輩子圖可以由幾棵樹(shù)組成，因?yàn)樗阉骺赡苡啥鄠€(gè)源頂點(diǎn)開(kāi)始重復(fù)進(jìn)行。因此深度優(yōu)先搜索的先輩子

4、圖的定義也和寬度優(yōu)先搜索稍有不同：G=(V,E),E=(v,v)E:vVvNIL深度優(yōu)先搜索的先輩子圖形成一個(gè)由數(shù)個(gè)深度優(yōu)先樹(shù)組成的深度優(yōu)先森林。E中的邊稱為樹(shù)枝。和寬度優(yōu)先搜索類似，深度優(yōu)先在搜索過(guò)程中也為結(jié)點(diǎn)著色以表示結(jié)點(diǎn)的狀態(tài)。每個(gè)頂點(diǎn)開(kāi)始均為白色，搜索中被發(fā)現(xiàn)時(shí)置為灰色，結(jié)束時(shí)又被置成黑色(即當(dāng)其鄰接表被完全檢索之后)。這一技巧可以保證每一頂點(diǎn)搜索結(jié)束時(shí)只存在于一棵深度優(yōu)先樹(shù)上，因此這些樹(shù)都是分離的。除了創(chuàng)建一個(gè)深度優(yōu)先森林外，深度優(yōu)先搜索同時(shí)為每個(gè)結(jié)點(diǎn)加蓋時(shí)間戳。每個(gè)結(jié)點(diǎn)v有兩個(gè)時(shí)間戳：當(dāng)結(jié)點(diǎn)v第一次被發(fā)現(xiàn)(并置成灰色)時(shí)記錄下第一個(gè)時(shí)間戳dv，當(dāng)結(jié)束檢查v的鄰接表時(shí)(并置v為黑色)

5、記錄下第二個(gè)時(shí)間截fv。許多圖的算法中都用到時(shí)間戳，他們對(duì)推算深度優(yōu)先搜索進(jìn)行情況是很有幫助的。下列過(guò)程DFS記錄了何時(shí)在變量du中發(fā)現(xiàn)結(jié)點(diǎn)u以及何時(shí)在變量fu中完成對(duì)結(jié)點(diǎn)u的檢索。這些時(shí)間戳為1到2|V|之間的整數(shù)，因?yàn)閷?duì)每一個(gè)v中結(jié)點(diǎn)都對(duì)應(yīng)一個(gè)發(fā)現(xiàn)事件和一個(gè)完成事件。對(duì)每一頂點(diǎn)u，有du<fu (1)在時(shí)刻du前結(jié)點(diǎn)u為白色，在時(shí)刻du和fu之間為灰色，以后就變?yōu)楹谏Ｏ旅娴膫未a就是一個(gè)基本的深度優(yōu)先搜索算法，輸人圖G可以是有向圖或無(wú)向圖，變量time是一個(gè)全局變量，用于記錄時(shí)間戳。 procedure DFS(G);- begin- 1 for 每個(gè)頂點(diǎn)uVG do- begin

6、- 2 coloruWhite;- 3 uNIL;- end;- 4 time0;- 5 for 每個(gè)頂點(diǎn)uVG do- 6 if coloru=White- 7 then DFS_Visit(G,u);- end;- procedure DFS_Visit(G,u);- begin- 1 coloruGray; 白色結(jié)點(diǎn)u已被發(fā)現(xiàn)- 2 dutimetime+1;- 3 for 每個(gè)頂點(diǎn)vAdju do 探尋邊(u,v)- 4 if colorv=White - then begin- 5 vu;- 6 DFS_Visit(G,v);- end;- 7 coloruBlack; 完成后置u為

7、黑色- 8 futimetime+1;- end;- 圖2說(shuō)明了DFS在圖1所示的圖上執(zhí)行的過(guò)程。被算法探尋到的邊要么為陰影覆蓋 (如果該邊為樹(shù)枝)，要么成虛線形式 (其他情況)。對(duì)于非樹(shù)枝的邊，分別標(biāo)明B(或F)以表示反向邊、交叉邊或無(wú)向邊。我們用發(fā)現(xiàn)時(shí)刻Z完成時(shí)刻的形式對(duì)結(jié)點(diǎn)加蓋時(shí)間戳。圖1 一個(gè)有向圖圖圖2 深度優(yōu)先搜索算法DFS在有向圖圖1上的執(zhí)行過(guò)程過(guò)程DFS執(zhí)行如下。第1-3行把所有結(jié)點(diǎn)置為白色，所有域初始化為NIL。第4行復(fù)位全局變量time，第5-7行依次檢索V中的結(jié)點(diǎn)，發(fā)現(xiàn)白色結(jié)點(diǎn)時(shí)，調(diào)用DFS_Visit去訪問(wèn)該結(jié)點(diǎn)。每次通過(guò)第7行調(diào)用DFS_Visit時(shí)，結(jié)點(diǎn)u就成為深度

8、優(yōu)先森林中一棵新樹(shù)的根，當(dāng)DFS返回時(shí)，每個(gè)結(jié)點(diǎn)u都對(duì)應(yīng)于一個(gè)發(fā)現(xiàn)時(shí)刻du和一個(gè)完成時(shí)刻fu。每次開(kāi)始調(diào)用DFS_Visit(u)時(shí)結(jié)點(diǎn)u為白色，第1行置u為灰色，第2行使全局時(shí)間變量增值并存于du中，從而記錄下發(fā)現(xiàn)時(shí)刻du，第3-6行檢查和u相鄰接的每個(gè)頂點(diǎn)v，且若v為白色結(jié)點(diǎn)，則遞歸訪問(wèn)結(jié)點(diǎn)v。在第3行語(yǔ)句中考慮到每一個(gè)結(jié)點(diǎn)vAdju時(shí)，我們可以說(shuō)邊(u,v)被深度優(yōu)先搜索探尋。最后當(dāng)以u(píng)為起點(diǎn)的所有邊都被探尋后，第7-8行語(yǔ)句置u為黑色并記錄下完成時(shí)間fu。算法DFS運(yùn)行時(shí)間的復(fù)雜性如何？DFS中第1-2行和5-7行的循環(huán)占用時(shí)間為O(V),這不包括執(zhí)行調(diào)用DFS_Visit過(guò)程語(yǔ)句所耗

9、費(fèi)的時(shí)間。事實(shí)上對(duì)每個(gè)頂點(diǎn)vV，過(guò)程DFS_Visit僅被調(diào)用一次，因?yàn)镈FS_Visit僅適用于白色結(jié)點(diǎn)且過(guò)程首先進(jìn)行的就是置結(jié)點(diǎn)為灰色，在DFS_Visit(v)執(zhí)行過(guò)程中，第3-6行的循環(huán)要執(zhí)行|Adjv|次。因?yàn)関V|Adjv| =(E)，因此執(zhí)行過(guò)程DFS_Visit中第2-5行語(yǔ)句占用的整個(gè)時(shí)間應(yīng)為(E)。所以DFS的運(yùn)行時(shí)間為(V+E)。練：算法設(shè)計(jì)郵電版 P200Procedure DFS(ga,g,i:integer); Var j:integer;BeginWVisitedi:=true; 訪問(wèn)頂點(diǎn)一出發(fā)點(diǎn)For i:=1 to ga.vex.;ast doIf (ga.mxI,j=1) and (not visitedj) Then DFS(ga,j); 從新頂點(diǎn)出發(fā) End.Procedure DFS1(gb,g,i:integer); Var p:link;BeginWrite(gb.adjlisti.first);Visite