算法分析與設計課件chapter-6圖的遍歷

1、南京理工大學6 圖遍歷Graph Traversal南京理工大學圖的遍歷是求解圖問題的基礎。和樹的遍歷類似，圖的遍歷希望從圖中某一頂點出發(fā)，對其余各個頂點都訪問一次，但比樹的遍歷要復雜得多。圖的任一頂點都有可能和其余頂點相鄰接，因此在訪問了某頂點后，可能沿著某條路徑搜索以后，又回到該頂點。通常有兩種遍歷圖的方法：深度優(yōu)先搜索、廣度優(yōu)先搜索。他們都適合于無向圖和有向圖。本章重點內(nèi)容是圖遍歷算法的復雜度分析，并學習圖遍歷算法的一些應用。南京理工大學深度優(yōu)先搜索(Depth-First Search, DFS)寬度優(yōu)先搜索(Breadth-First Search, BFS)圖的兩種遍歷方法 南京理

2、工大學深度優(yōu)先搜索(Depth-First Search, DFS) 給定有向或是無向圖G(V,E)，DFS工作過程如下：1. 將所有的頂點標記為”unvisited”。2. 選擇一個起始頂點,不妨稱為v V,并將之標記為”visited”。3. 選擇與v相鄰的任一頂點，不妨稱之為w，將w標記為”visited”。4. 繼續(xù)選擇一個與w相鄰且未被訪問的頂點作為x；將x標記為”visited”。繼續(xù)選擇與x相鄰且未被訪問的頂點。此過程一直進行，直到發(fā)現(xiàn)一個頂點y，鄰接于y的所有頂點都已經(jīng)被標記為”visited”。此時，返回到最近訪問的頂點，不妨稱之為z，然后訪問和z相鄰且標記為”unvisit

3、ed”的頂點。6. 上述過程一直進行，直到返回到起始頂點v。 南京理工大學輸入：無向圖或有向圖G= (V,E)輸出：深度優(yōu)先搜索樹(森林)中每個頂點的先序號、后序號1. predfn0; postdfn0 /計數(shù)器，在使用DFS解決某些實際問題時用到2. for vV3. visitedv false4. end for5. for vV /從一個頂點v出發(fā)，可能無法遍歷全部頂點6. if visitedv = false then dfs(v)7. end fordfs(v)1. visitedv true2. predfnpredfn+13. for (v,w)E4. if visited

4、w=false then dfs(w)5. end for6. postdfnpostdfn+1.南京理工大學深度優(yōu)先搜索生成樹(depth-first search spanning tree)深度優(yōu)先搜索生成森林(depth-first search spanning forest)predfn：在圖的深度優(yōu)先搜索生成樹(森林)中頂點的先序號。所謂先序號，是指按照先序方式訪問該生成樹，該頂點的序號。postdfn：在圖的深度優(yōu)先搜索生成樹(森林)中頂點的后序號。所謂后序號，是指按照后序方式訪問該生成樹，該頂點的序號。邊(v,w)已被探測，含義是：在調(diào)用dfs(v)的過程中，檢查(v,w)以

5、測試w是否已經(jīng)被訪問過(”visited”)。南京理工大學無向圖情形無向圖G= (V,E)，深度優(yōu)先遍歷后，G中的邊可以分為如下類型：樹邊(Tree edges) 深度優(yōu)先搜索生成樹中的邊：探測邊(v,w)時，w是“unvisited”狀態(tài)，則邊(v,w)是樹邊。回邊(Back edges)G中除卻樹邊的所有其它邊。南京理工大學decbafghijdecbafghij1,102,93,34,25,110,49,58,67,76,8樹邊回邊postdfn=1: 該頂點是第一個不能繼續(xù)向深度前進的頂點； 或是稱為第一個完成深度搜索的頂點。南京理工大學有向圖情形有向圖G= (V,E)，深度優(yōu)先遍歷后

6、，會生成一個或是多個(有向)深度優(yōu)先搜索生成樹，樹的多少取決于起始點的選擇。G中的邊可以分為如下4種類型：樹邊(Tree edges) 深度優(yōu)先搜索生成樹中的邊：探測邊(v,w)時，w是“unvisited”狀態(tài)，則邊(v,w)是樹邊?；剡?Back edges)在迄今為止所構(gòu)建的深度優(yōu)先搜索生成樹中，w是v的祖先，并且在探測(v,w)時，w已經(jīng)被標記為”visited”,則(v,w)為回邊。前向邊(Forward edges)在迄今為止所構(gòu)建的深度優(yōu)先搜索生成樹中，w是v的后裔，并且在探測(v,w)時，w已經(jīng)被標記為”visited”,則(v,w)為前向邊。橫跨邊(Cross edges)所

7、有其他的邊。南京理工大學decbaf樹邊前向邊回邊橫跨邊Case 1: 從頂點a開始，依次訪問a,b,e,f; c,ddecbaf1,42,34,23,15,66,5Case 2: 從頂點a開始，依次訪問a,f,e,b; c,ddbcfae1,42,23,14,35,66,5南京理工大學時間復雜度分析假設圖有n個頂點，m條邊。 (m+n) 南京理工大學南京理工大學南京理工大學南京理工大學深度優(yōu)先搜索的應用圖的無回路性拓撲排序?qū)ふ覉D的關節(jié)點強連通分支網(wǎng)絡頁面檢索南京理工大學圖回路目標：若G= (V,E)，是一個有n個頂點和m條邊的有向或是無向圖。要測試G中是否包含有一個回路。方法：對G施加深度優(yōu)

8、先搜索，如果探測到一個回邊，那么可以判定G中含有回路；否則G中無回路。注意：如果G是連通的無向圖，則不需要對G進行深度優(yōu)先搜索來判定是否有回路。G無回路，當且僅當|E|=|V|-1。南京理工大學拓撲排序(Topological sorting) 給定一個有向無回路圖(Directed Acyclic Graph, DAG) G=(V,E)。拓撲排序是為了找到圖頂點的一個線性序，使得：如果(v,w) E,那么，在線性序中，v在w之前出現(xiàn)。decbafga b c d e f g我們假設在DAG中只有唯一一個入度為0的頂點；如果有一個以上的頂點入度為0，可以通過添加一個新的頂點s，然后將s指向所有

9、入度為0的頂點，這樣s就成為唯一一個入度為0的頂點。南京理工大學拓撲排序的實現(xiàn)：從入度為0的頂點開始，對DAG實施深度優(yōu)先搜索。遍歷完成后，計數(shù)器postdfn恰好對應于一個在DAG中頂點的反拓撲序。得到拓撲序：在DFS算法中恰當位置增加輸出語句(step 6)，然后將輸出結(jié)果反轉(zhuǎn)。在DFS算法中恰當位置增加頂點入棧(step 6)操作，然后依次取棧頂元素輸出。南京理工大學尋找關節(jié)點(Finding articulation points in a graph*)關節(jié)點: 給定無向圖G(V,E)，|V|2。稱v G 為一關節(jié)點，當且僅當存在另外兩個不同的頂點u G和w G,并且u與v之間的任意

10、路徑均必須經(jīng)由v通過。顯然，如果G是連通的，那么在移除關節(jié)點和與其關聯(lián)的邊后，圖變?yōu)椴贿B通的。雙連通：一個圖如果是連通的，并且沒有關節(jié)點，那么稱該圖是雙連通的。南京理工大學網(wǎng)絡頁面檢索深度優(yōu)先搜索是一種在開發(fā)爬蟲早期使用較多的方法。它的目的是要達到被搜索結(jié)構(gòu)的葉結(jié)點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇后，被鏈接的HTML文件將執(zhí)行深度優(yōu)先搜索，即在搜索其余的超鏈接結(jié)果之前必須先完整地搜索單獨的一條鏈。深度優(yōu)先搜索沿著HTML文件上的超鏈走到不能再深入為止，然后返回到某一個HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說

11、明搜索已經(jīng)結(jié)束。優(yōu)點是能遍歷一個Web 站點或深層嵌套的文檔集合；缺點是因為Web結(jié)構(gòu)相當深,，有可能造成一旦進去，再也出不來的情況發(fā)生。南京理工大學廣度優(yōu)先搜索(Breadth-First Search, BFS)思路：在訪問一個頂點v后，接下來依次訪問鄰接于v的所有頂點。對應的搜索樹稱之為廣度優(yōu)先搜索生成樹。實現(xiàn)：使用隊列(Queue)BFS同樣既適用于有向圖，亦適用于無向圖。在無向圖中，邊分為：樹邊或者是橫跨邊。在有向圖中，邊分為：樹邊，回邊及橫跨邊。不存在前向邊。南京理工大學BFS算法輸入：無向圖或有向圖G= (V,E)輸出：廣度優(yōu)先搜索樹中每個頂點的編號(編號：按廣度優(yōu)先的原則，該頂

12、點被訪問的次序)1. bfn02. for vV3. visitedv false4. end for5. for vV6. if visitedv = false then bfs(v)7. end for bfs(v)1. Qv2. visitedv true3. while Q /to be visited4. vpop(Q)bfnbfn+1for (v,w)E if visitedw=false then Push(w,Q)9. visitedwtrue end ifend for12. end while南京理工大學decbafghijabgcfhdeijQueue時間復雜度： (m+n) 無向圖BFS實例47樹邊橫跨邊decbafghij123568910南京理工大學acbdef5421abcdfe63有向圖BFS實例思考：為什么有向圖的BFS中不會