深度優(yōu)先探尋算法DFS

本文格式為Word版，下載可任意編輯——深度優(yōu)先探尋算法DFS

深度優(yōu)先探尋算法DFS

深度優(yōu)先探尋算法DFS

===

1.首先選定圖的類別（有向圖、無(wú)向圖），再選定圖的存儲(chǔ)結(jié)構(gòu)，根據(jù)輸入的頂點(diǎn)或者邊建立圖；并把相應(yīng)的鄰接表或者鄰接矩陣輸出；2.根據(jù)已有的鄰接矩陣或鄰接表用遞歸方法編寫(xiě)深度優(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è)元素。

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(inti)深度優(yōu)先遍歷算法外沒(méi)有過(guò)多解釋。

====深度優(yōu)先探尋DFS

正如算法名稱那樣，深度優(yōu)先探尋所遵循的探尋策略是盡可能“深〞地探尋圖。在深度優(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ù)組成，由于探尋可能由多個(gè)源頂點(diǎn)開(kāi)始重復(fù)進(jìn)行。因此深度優(yōu)先探尋的先輩子圖的定義也和寬度優(yōu)先探尋稍有不同：

Gπ=(V,Eπ),Eπ={(π[v],v)∈E:v∈V∧π[v]≠NIL}

深度優(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í)置為灰色，終止時(shí)又被置成黑色(即當(dāng)其鄰接表被完全檢索之后)。這一技巧可以保證每一頂點(diǎn)探尋終止時(shí)只存在于一棵深度優(yōu)先樹(shù)上，因此這些樹(shù)都是分開(kāi)的。

除了創(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í)間戳d[v]，當(dāng)終止檢查v的鄰接表時(shí)(并置v為黑色)記錄下其次個(gè)時(shí)間截f[v]。大量圖的算法中都用到時(shí)間戳，他們對(duì)推算深度優(yōu)先探尋進(jìn)行狀況是很有幫助的。

以下過(guò)程DFS記錄了何時(shí)在變量d[u]中發(fā)現(xiàn)結(jié)點(diǎn)u以及何時(shí)在變量f[u]中完成對(duì)結(jié)點(diǎn)u的檢

深度優(yōu)先探尋算法DFS

索。這些時(shí)間戳為1到2|V|之間的整數(shù)，由于對(duì)每一個(gè)v中結(jié)點(diǎn)都對(duì)應(yīng)一個(gè)發(fā)現(xiàn)事件和一個(gè)完成事件。對(duì)每一頂點(diǎn)u，有

d[u]f[u](1)

在時(shí)刻d[u]前結(jié)點(diǎn)u為白色，在時(shí)刻d[u]和f[u]之間為灰色，以后就變?yōu)楹谏?/p>

下面的偽代碼就是一個(gè)基本的深度優(yōu)先探尋算法，輸人圖G可以是有向圖或無(wú)向圖，變量time是一個(gè)全局變量，用于記錄時(shí)間戳。

procedureDFS(G);

-begin

-1for每個(gè)頂點(diǎn)u∈V[G]do

-begin

-2color[u]←White;

-3π[u]←NIL;

-end;

-4time←0;

-5for每個(gè)頂點(diǎn)u∈V[G]do

-6ifcolor[u]=White

-7thenDFS_Visit(G,u);

-end;

-

-procedureDFS_Visit(G,u);

-begin

-1color[u]←Gray;Δ白色結(jié)點(diǎn)u已被發(fā)現(xiàn)

-2d[u]←time←time+1;

-3for每個(gè)頂點(diǎn)v∈Adj[u]doΔ探尋邊(u,v)

-4ifcolor[v]=White

-thenbegin

-5π[v]←u;

-6DFS_Visit(G,v);

-end;

-7color[u]←Black;Δ完成后置u為黑色

-8f[u]←time←time+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è)有向圖圖

深度優(yōu)先探尋算法DFS

圖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就成為深度優(yōu)先森林中一棵新樹(shù)的根，當(dāng)DFS返回時(shí)，每個(gè)結(jié)點(diǎn)u都對(duì)應(yīng)于一個(gè)發(fā)現(xiàn)時(shí)刻d[u]和一個(gè)完成時(shí)刻f[u]。

每次開(kāi)始調(diào)用DFS_Visit(u)時(shí)結(jié)點(diǎn)u為白色，第1行置u為灰色，第2行使全局時(shí)間變量增值并存于d[u]中，從而記錄下發(fā)現(xiàn)時(shí)刻d[u]，第3-6行檢查和u相鄰接的每個(gè)頂點(diǎn)v，且若v為白色結(jié)點(diǎn)，則遞歸訪問(wèn)結(jié)點(diǎn)v。在第3行語(yǔ)句中考慮到每一個(gè)結(jié)點(diǎn)v∈Adj[u]時(shí)，我們可以說(shuō)邊(u,v)被深度優(yōu)先探尋探尋。最終當(dāng)以u(píng)為起點(diǎn)的所有邊都被探尋后，第7-8行語(yǔ)句置u為黑色并記錄下完成時(shí)間f[u]。

算法DFS運(yùn)行時(shí)間的繁雜性如何？DFS中第1-2行和5-7行的循環(huán)占用時(shí)間為O(V),這不包括執(zhí)行調(diào)用DFS_Visit過(guò)程語(yǔ)句所花費(fèi)的時(shí)間。事實(shí)上對(duì)每個(gè)頂點(diǎn)v∈V，過(guò)程DFS_Visit僅被調(diào)用一次，由于DFS_Visit僅適用于白色結(jié)點(diǎn)且過(guò)程首先進(jìn)行的就是置結(jié)點(diǎn)為灰色，在DFS_Visit(v)執(zhí)行過(guò)程中，第3-6行的循環(huán)要執(zhí)行|Adj[v]|次。由于∑v∈V|Adj[v]|=θ(E)，因此執(zhí)行過(guò)程DFS_Visit中第2-5行語(yǔ)句占用的整個(gè)時(shí)間應(yīng)為θ(E)。所以DFS的運(yùn)行時(shí)間為θ(V+E)。

深度優(yōu)先探尋算法DFS

練：《算法設(shè)計(jì)》郵電版P200

ProcedureDFS(ga,g,i:integer);

Varj:integer;

Begin

Write(ga.vex.data[i]);

Visited[i]:=true;{訪問(wèn)頂點(diǎn)一出發(fā)點(diǎn)}Fori:=1toga.vex.;astdo

If(ga.mx[I,j]=1)and(notvisited[j])

ThenDFS(ga,j);{從新頂點(diǎn)出發(fā)}

End.

ProcedureDFS1(gb,g,i:integer);

Varp:link;

Begin

Write(gb.adjlist[i].first);

Visited[i]:=true;{訪問(wèn)頂點(diǎn)}

P:=gb.adjlist[i].first;{取頂點(diǎn)的邊表指針}Whilepn