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

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

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

3、是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的頂點(diǎn)，如果它還有以此為起點(diǎn)而未探測到的邊，就沿此邊繼續(xù)漢下去。當(dāng)結(jié)點(diǎn)v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v有那條邊的始結(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的結(jié)點(diǎn)，則選擇其中一個作為源結(jié)點(diǎn)并重復(fù)以上過程，整個進(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時，深度優(yōu)先搜索將置v的先輩域v為u。和寬度優(yōu)先搜索不同的是，前者的先輩子圖形成一棵樹，而后者產(chǎn)生的先輩子圖可以由幾棵樹組成，因為搜索可能由多個源頂點(diǎn)開始重復(fù)進(jìn)行。因此深度優(yōu)先搜索的先輩子

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

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

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

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

9、費(fèi)的時間。事實上對每個頂點(diǎn)vV，過程DFS_Visit僅被調(diào)用一次，因為DFS_Visit僅適用于白色結(jié)點(diǎn)且過程首先進(jìn)行的就是置結(jié)點(diǎn)為灰色，在DFS_Visit(v)執(zhí)行過程中，第3-6行的循環(huán)要執(zhí)行|Adjv|次。因為vV|Adjv| =(E)，因此執(zhí)行過程DFS_Visit中第2-5行語句占用的整個時間應(yīng)為(E)。所以DFS的運(yùn)行時間為(V+E)。練：算法設(shè)計郵電版 P200Procedure DFS(ga,g,i:integer); Var j:integer;BeginWVisitedi:=true; 訪問頂點(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