本科畢業(yè)論文圖的深度優(yōu)先遍歷及應用

1、本科畢業(yè)論文（設計）論文(設計)題目： 圖的深度優(yōu)先遍歷及應用 專 業(yè)： 計算機科學與技術 班 級： 學 號： 學 生 姓 名： 摘要圖是一個最基本、最有表現(xiàn)力的結構，可以用于表示具有各種復雜關系的數(shù)據(jù)集合，在實際應用中無處不在。雖然問題的狀態(tài)可以用圖來表示，但問題的求解則往往是從狀態(tài)圖中尋找某個狀態(tài)，或是尋找從一個狀態(tài)到另一個狀態(tài)的路徑。實現(xiàn)這一求解的過程需要逐步探索與問題有關的各種狀態(tài)，這即是搜索。這里我們將討論基于深度優(yōu)先搜索圖的算法，以及該算法的一些相關性質，主要包括：括號定理、后裔區(qū)間的嵌套性質和白色路徑性質，和由此引出的對邊的分類。并給出其應用：一方面是作為基礎應用于求無向圖中連通

2、分量的個數(shù)和求解無向圖中通過給定頂點V的簡單回路的算法中；另一方面是對基于DFS 的圖的雙向連通性的判斷。關鍵詞深度優(yōu)先遍歷；連通分量；簡單回路；掛接點AbstractGraphs is the most basic and performance data structure in computer science, it can used for meaning that the data that have various complicated relation gathers, and algorithms for working with them are fundamental

3、to the field. Although the status of problem can be meant with Graphs,the solving of problem then usually looks for a certain status from the state graph,or looks for from a path that the status arrives another status.Carry out this various status that the process solving needs to gradually investig

4、ate to have something to do with problem,this is to search. Here we discuss algorithms based on searching a graph using depth-first search, as well as some connected property, including Parenthesis theorem、Nesting of descendants intervals、White-path theorem and Classification of edges derived from t

5、hese.Some applications are also given: One is as foundation applied to found the number of connected components in no directed graph; the other hand is to according to the double of DFS graph to connect sexual judgment.Key wordsDFS(Depth First Search); connected components; simple back track; atrpoi

6、nt 目錄 緒論11. 深度優(yōu)先遍歷算法的思想及算法12. 深度優(yōu)先遍歷算法的性質22.1.括號性質及其相應性質22.2.邊的分類43. 深度優(yōu)先遍歷算法的應用43.1.作為基礎應用在其他算法中43.1.1.求無向圖中連通分量的個數(shù)43.1.2. 求解無向圖中通過給定頂點V的簡單回路43.2. 基于DFS 的圖的雙向連通性的判斷53.2.1.基本概念53.2.2. 圖的雙向連通性判斷的理論基礎53.2.3. 圖的雙向連通性判斷方法及實現(xiàn)63.2.4. 查找掛接點的DFS 動態(tài)樹示例74.小結8致謝9參考文獻9圖的深度優(yōu)先遍歷及應用緒論算法分析與設計是計算機科學的靈魂，圖論算法是算法中一重要的組

7、成部分，可以用于表示具有各種復雜關系的數(shù)據(jù)結構，在實際中應用廣泛。雖然問題的狀態(tài)可以用圖來表示，但問題的求解則往往是從狀態(tài)圖中尋找某個狀態(tài)，或是尋找從一個狀態(tài)到另一個狀態(tài)的路徑。實現(xiàn)這一求解的過程需要逐步探索與問題有關的各種狀態(tài)，這即是搜索。從一個圖的搜索算法中可以發(fā)現(xiàn)很多有關于圖的結構的信息，因而搜索圖的技術又是圖論算法領域的核心。深度優(yōu)先搜索算法是圖論最常用的算法之一，是圖論中很多其它算法的基礎，是圖論中的核心算法之一，因此對該算法進行算法分析與設計具有重要的意義。本論題主要研究的內容包括，總結圖的深度優(yōu)先遍歷算法發(fā)現(xiàn)很多有關于圖的結構的信息，以及該算法的一些相關性質。并給出其應用：一方面

8、是作為基礎應用于求無向圖中連通分量的個數(shù)和求解無向圖中通過給定頂點V的簡單回路的算法中；另一方面是基于DFS 的圖的雙向連通性的判斷。1. 深度優(yōu)先遍歷算法的思想及算法 所謂"深度"是對產(chǎn)生問題的狀態(tài)結點而言的，"深度優(yōu)先"是一種控制結點擴展的策略，這種策略是優(yōu)先擴展深度大的結點，把狀態(tài)向縱深發(fā)展。深度優(yōu)先搜索也叫做DFS法(Depth First Search)。在深度優(yōu)先搜索中，邊是從那些最近發(fā)現(xiàn)的但還有未被探測到的邊存在的結點v中探測出來。當v的所有邊都探測完，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的始節(jié)點。這一過程一直進行到我們發(fā)現(xiàn)所有初始源結點可達到的

9、結點為止。如果還存在沒發(fā)現(xiàn)的結點，選其中一個結點作為新的源結點并從該結點開始重復搜索。整個過程反復執(zhí)行到所有結點都找到為止。在深度優(yōu)先搜索中為了記錄結點的探索狀態(tài)，我們采用在搜索的過程中對結點染不同的色來描述它們的狀態(tài)。每個結點初態(tài)是白色，搜索過程被發(fā)現(xiàn)的時候將其染成灰色，當它的鄰接表完全檢查完的時候染成黑色。這一技巧保證每個結點在搜索結束時只在一顆深度優(yōu)先搜索樹中，并使這些樹分開。除了創(chuàng)建一個深度優(yōu)先搜索森林外，為了方便，深度優(yōu)先搜索給每個結點都標上時間郵戳。每個結點v有兩個時間郵戳：第一個時間郵戳dv記錄了v首次發(fā)現(xiàn)（即變灰時）的時間，第二個時間郵戳fv記錄了搜索完成（即涂黑的v）的時間。

10、這些時間郵戳對推算深度優(yōu)先搜索進行情況是很有幫助的，并被使用于很多圖論算法中。深度優(yōu)先搜索的具體思想是： 1、從圖的指定頂點V出發(fā)。 2、先訪問頂點V，并將其標記為灰色。3、依次從V的未被訪問過的鄰接頂點W出發(fā)進行深度優(yōu)先搜索（算法需要為V的鄰接結點假定一種順序）。直到圖中與V連通的所有頂點都訪問過。 4、如果圖中還有未訪問頂點，則選一未訪問頂點。由它出發(fā)重復上述過程。直到圖中所有頂點都被訪問為止。 其算法為：DFS(G) for each vertex u Î G->V u->color = WHITE; time = 0; for each vertex u 

11、6; G->V if (u->color = WHITE) DFS_Visit(u); DFS_Visit(u) u->color = GREY; time = time+1; d u = time; for each v Î u->Adj if (v->color = WHITE) DFS_Visit(v); u->color = BLACK; time = time+1; f u= time; 深度優(yōu)先搜索過程記錄：d u即發(fā)現(xiàn)結點u的時間，f u即遍歷完成的時間，這些時間郵戳是間于1和2|V|的整數(shù)，以后對每個|V|結點有一個發(fā)現(xiàn)事件和一個結

12、束事件。對每個結點u，有du<fu。結點u在時間du前是白色，時間du到fu內是灰色，此后是黑色。算法時間復雜度分析：DFS(G)中循環(huán)所占用的時間為O(V)，但這并不包括調用DFS_Visit過程語句所耗費的時間。事實上對V中的每個頂點DFS_Visit僅被調用一次，因為DFS_Visit僅適用于白色頂點，并在執(zhí)行完后將其涂成灰色。而在DFS_Visit執(zhí)行的過程只中所耗費的時間為O(E)，所以算法的運行時間為O(V+E)。2.深度優(yōu)先遍歷算法的性質2.1括號性質及其相應性質依據(jù)深度優(yōu)先搜索可以獲得有關圖的結構的大量信息。也許深度優(yōu)先搜索的最基本的特征是它的先輩子圖G，形成一個由樹組成

13、的森林，這是因為深度優(yōu)先樹的結構準確反映了DFS_Visit中遞歸調用的結構的緣故，即u=v當且僅當在搜索u的鄰接表過程中調用了過程DFS_Visit(v)。另外，結點u是深度優(yōu)先搜索森林中結點v 的子孫當且僅當v在u是灰色時被發(fā)現(xiàn)。 深度優(yōu)先搜索另一個重要的性質是發(fā)現(xiàn)和結束時間有括號結構。如果我們把發(fā)現(xiàn)結點u表示為“(u”，把結束表示為“u)”，那么發(fā)現(xiàn)和結束的過程，從括號的后裔區(qū)間的嵌套性質上講，就得到一個良好的表達。例如，圖示2.1(a)圖深度優(yōu)先搜索對應了圖2.1(b)中的括號表示。另一個確定括號結構條件的是以下給出的定理 。 （1） 括號性質 在對有向圖或無向圖G=(V,E)的任何深

14、度優(yōu)先搜索中，對于圖中任意兩結點u和v，下述三個條件中有且僅有一條成立：區(qū)間du，fu和區(qū)間dv，fv是完全分離的；區(qū)間du，fu完全包含于區(qū)間dv，fv中且在深度優(yōu)先樹中u是v的后裔； 區(qū)間dv，fv完全包含于區(qū)間du，fu中且在深度優(yōu)先樹中v是u的后裔。 （2）后裔區(qū)間的嵌套性質 在某一有向（或無向）圖中的深度優(yōu)先搜索森林中，結點v是結點u的子孫當且僅當du<dv<fv<fu 。（3）白色路徑性質 在一有向（或無向）圖G=（V，E）的深度優(yōu)先搜索森林中，結點v是結點u的子孫當且僅當在搜索到u的時間du，結點u可以順著一條包含所有白色結點的路徑到達v。2.2邊的分類 深度優(yōu)

15、先搜索另一個有趣的性質是，可以通過搜索對輸入圖G=（V，E）的邊進行歸類。這種歸類可以發(fā)現(xiàn)圖的很多重要信息。根據(jù)在圖G上進行深度優(yōu)先搜索所產(chǎn)生的深度優(yōu)先森林G，我們可以把圖的邊分為四種類型。1、樹邊，是深度優(yōu)先森林G中的邊，如果結點v是在探尋邊(u，v)時第一次被發(fā)現(xiàn)，那么邊(u，v)就是一個樹邊。 2、反向邊，是深度優(yōu)先樹中連結結點u到它的祖先v的那些邊，環(huán)也被認為是反向邊。 3、正向邊，是指深度優(yōu)先樹中連接頂點u到它的后裔的非樹邊的邊。 4、交叉邊，是指所有其他類型的邊，它們可以連結同一棵深度優(yōu)先樹中的兩個結點，只要一結點不是另一結點的祖先，也可以連結分屬兩棵深度優(yōu)先樹的結點。 DFS算法

16、修改成當它對邊計數(shù)時完成對邊的分類。關鍵思想是每條邊（u，v）當首次被探測到（除前向邊和交叉邊不用區(qū)分）時，可以由結點v的顏色決定： 1、白色樹邊 2、灰色反向邊 3、黑色前向或交叉邊 由以上規(guī)則我們可以發(fā)現(xiàn)在深度優(yōu)先搜索無向圖時不會出現(xiàn)正向邊和交叉邊。即可得到定理：定理1在對無向圖G進行深度優(yōu)先搜索的過程中，G的每條邊要么是樹邊要么是反向邊。證明:設(u，v)為G的任意一邊，不失一般性，假定du<dv。則因為v在u的鄰接表中，所以我們必定在完成u之前就已發(fā)現(xiàn)并完成v。如果邊(u，v)第一次是按從u到v的方向被探尋到，那么(u，v)必是一樹枝。如果(u，v)第一次是按從v到u的方向被探尋

17、到，則由于該邊被第一次探尋時u依然是灰色結點，所以(u，v)是一條反向邊。(證畢)1.2.3. 深度優(yōu)先遍歷算法的應用 3.1 作為基礎應用在其他算法中4,5深度優(yōu)先遍歷算法作為一個遞歸的過程，以一種自然的方式進行搜索，它用一個棧來維護即將被處理的結點，本質上DFS的遞歸結構可以看做把結點堆入棧以備后續(xù)處理，同時移動到更新發(fā)現(xiàn)的結點。因此，只要以深度優(yōu)先遍歷算法為基礎，并進行一些簡單的設置和改進，就可以應用于其他算法中，下面就是兩個以它為基礎的簡單算法：3.1.1 求無向圖中連通分量的個數(shù) 為求解該問題只要在DFS算法中加入一個計數(shù)器count，每調用一次DFS，就把count的值加1，則最后

18、count的值就是無向圖中連通分量的個數(shù)。3.1.2 求解無向圖中通過給定頂點Vi的簡單回路的算法從給定的頂點v開始進行深度優(yōu)先搜索，搜索過程中每訪問一個結點，判斷其是否為v，若是v，則說明找到一條回路，否則繼續(xù)搜索。因此，可以設置一個順序棧來記錄構成回路的結點序列，并把訪問結點的操作改為頂點入棧，從某一頂點搜索完便回溯，并進行出棧操作，另外，需再設置一個標志found，置其初值為false，當找到回路后則置其值為true。如此棧中的頂點序列便是一條簡單回路，若棧為空，則不存在簡單回路。如此便可找到可找到無向圖中通過頂點Vi的簡單回路4。3.2 基于DFS的圖的雙向連通性的判斷3.2.1 基本

19、概念6,7（1）DFS 動態(tài)樹我們知道描述DFS 函數(shù)遞歸調用的樹稱為深度優(yōu)先樹。在深度優(yōu)先樹中，對于那些已經(jīng)訪問過的結點如果我們?yōu)槠涮砑右恍┩獠拷Y點來表示跳過相應的遞歸調用，將得到DFS 動態(tài)性的緊湊表達方式，這就是DFS動態(tài)生成樹，簡稱DFS動態(tài)樹。DFS 動態(tài)樹是圖的一種表達方式，其頂點對應于圖的每個頂點，其邊對應于圖的每一條邊。對于圖中的每條邊，DFS動態(tài)樹中有兩個鏈接，分別對應于兩次碰到該邊的情形。第一個鏈接指向未加陰影結點，或者對應于遞歸調用（若它是內部結點），稱作樹鏈接；或者跳過遞歸調用，因為它定位到一個正進行遞歸調用的祖先（若它是外部結點），稱作后向鏈接。第二個鏈接指向帶陰影的

20、外部結點，而且總與跳過遞歸調用對應，或者是因為返回到它的父親，稱作父鏈接；或者是因為它定位到正進行遞歸調用的父親的一個后代，稱作下向鏈接。（如圖3-2（a）與3-2(b)所示）（2）掛接點和雙向連通圖假若在刪去結點v 以及和v 相關聯(lián)的各邊之后，將圖的一個連通分量分割成兩個或兩個以上的連通分量，則稱結點v 為該圖的一個掛接點。一個沒有掛接點的連通圖稱為雙向連通圖。在雙向連通圖上，任意兩個結點之間至少存在兩條路徑，則在刪去某個結點以及依附于該結點的各邊時也不破壞圖的連通性。每一個雙向連通圖都是邊連通的，但每一個邊連通圖不一定為雙向連通的。3.2.2 圖的雙向連通性判斷的理論基礎DFS 策略是圖的

21、雙向連通性判斷的理論基礎。下面的程序是一個訪問連通圖中所有結點并檢查所有邊的DFS 遞歸函數(shù)實現(xiàn)，這個實現(xiàn)使用一個全局數(shù)組pre 和一個增量計數(shù)器cnt來標記結點，通過標記結點被訪問的順序達到訪問連通圖中所有結點的目的。pre 數(shù)組實際存放的是DFS 動態(tài)樹中內部結點的前序編號。在該程序中，將一條邊傳遞給遞歸函數(shù)，而不是傳遞目標頂點，這是因為邊可以標記如何到達頂點。static int cnt, premaxV;void dfs (Graph G, Edge e) link t;int w = e.w;prew = cnt+;for (t = G->adjw; t != NULL; t

22、= t->next)if (pret->v = -1) dfs (G, EDGE(w, t->v);void Graph_search(Graph G) int v, cnt = 0;for (v = 0; v < G->V; v+) prev = -1;for (v = 0; v < G->V; v+)if (prev = -1) dfs(G, EDGE(v, v);3.2.3 圖的雙向連通性判斷方法及實現(xiàn)3.2.3.1 判斷方法因為雙向連通圖是不含掛接點的圖，因此判斷一個圖是否為雙向連通圖這一問題便轉化為求一個圖中是否存在掛接點。只要能從圖中找出掛

23、接點，則此圖一定不是雙向連通圖。在DFS動態(tài)樹中，有兩類掛接點，它們的特性分別如下:（1） 若DFS 動態(tài)樹的根結點為掛接點當且僅當其至少有兩個子女。證明：因為圖中不存在連接不同子樹中結點的邊，因此，若刪去根結點，DFS 樹便變成DFS 森林，所以若DFS 動態(tài)樹的根有兩棵或兩棵以上的子樹，則根結點必為掛接點。（2） 若DFS 動態(tài)樹中某個非葉子結點v，其某棵子樹的根和子樹中的其它結點均沒有指向v 的祖先的后向邊，則結點v 為掛接點。證明：因為，若刪去v，則其子樹和圖的其它部分被分割開來，所以對DFS 動態(tài)樹中某個非葉子結點v，其某棵子樹的根和子樹中的其它結點均沒有指向v 的祖先的后向邊，則結

24、點v 為掛接點。為了找出掛接點的集合，在圖G 上執(zhí)行深度優(yōu)先搜索遍歷，在遍歷的過程中，對每個頂點v 保持兩個編號: 前序編號prev和最低前序編號lowv，prev只是深度優(yōu)先搜索算法中的cnt，每次調用深度優(yōu)先搜索算法時，cnt加1，lowv初始化為prev，但在后來的遍歷過程中可以改變，對于每一個訪問的頂點v，其最低前序編號lowv計算如下: prev lowv=Min loww，w是頂點v在生成樹上的孩子頂點，（v，w）E prek，k頂點v生成樹上由后向邊連接的祖先頂點，（v，k）E若對于某個頂點v，存在孩子頂點w且lowwprev，則該頂點v必為掛接點。因為，當w是v的孩子頂點時，l

25、oww prev，表明以w為根的子樹和子樹中的頂點均無指向v的祖先的后向邊。3.2.3.2 方法實現(xiàn)利用遞歸函數(shù)Dfs_articul 求圖中的關節(jié)點。它使用一個計數(shù)器bnct和一個掛接點數(shù)組ac，low數(shù)組跟蹤每一個頂點的最低前序編號。static int cnt, acnt, root, rootdegree, premaxV,lowmaxV,acmaxV;void Graph_articul(Graph G) int v; link t;for (v = 0; v < G->V; v+) prev = -1;cnt=0; / 圖的頂點計數(shù)器acnt=0; / 圖的掛接點計數(shù)器

26、rootdegree=0; / 根頂點的度Dfs_articul(G, EDGE(root, root);void Dfs_articul(Graph G, Edge e) link t;int w, v = e.w;atrpoint=FALSE;/ atrpoint 標記當前頂點v 是否為掛接點prev = cnt+; lowv = prev;for (t = G->adjv; t != NULL; t = t->next)if (prew = t->v = -1) /樹邊 Dfs_articul(G, EDGE(v, w);if(v=root) /處理根頂點 rootdegree+;if(rootdegree=2) atrpoint=TRUE;else / 處理非根頂點 if (lowv > loww) lowv = loww;if (loww >= prev) atrpoint=TRUE;else if (v != e.v)