《算法設計與分析》課件 第7章 圖算法

算法設計與分析圖算法主要內(nèi)容深度優(yōu)先搜索廣度優(yōu)先搜索單源最短路徑多源最短路徑1基本概念1基本概念：圖的遍歷圖的遍歷是求解圖問題的基礎。和樹的遍歷類似，圖的遍歷希望從圖中某一頂點出發(fā)，對其余各個頂點都訪問一次，但比樹的遍歷要復雜得多。圖的任一頂點都有可能和其余頂點相鄰接，因此在訪問了某頂點后，可能沿著某條路徑搜索以后，又回到該頂點。通常有兩種遍歷圖的方法：深度優(yōu)先搜索、廣度優(yōu)先搜索。他們都適合于無向圖和有向圖。1深度優(yōu)先搜索1深度優(yōu)先搜索流程1深度優(yōu)先搜索流程32014v=2的DFS序列：21034遍歷過程結束32014DFS思路：距離初始頂點越遠越優(yōu)先訪問！1深度優(yōu)先搜索通過對圖G進行深度優(yōu)先搜索，按照節(jié)點的遍歷順序會生成一棵樹，稱為深度優(yōu)先搜索生成樹，當原圖為非聯(lián)通時，會生成深度優(yōu)先搜索生成森林每個節(jié)點標注兩個屬性，一個稱為先序號(用predfn表示)，另一個屬性稱為后序號(用postdfn表示)。1深度優(yōu)先搜索dfs(v)函數(shù)共被調(diào)用了n次，而每次調(diào)用dfs(v)函數(shù)都需要對節(jié)點v所連的邊都遍歷一次(dfs(v)函數(shù)中的for循環(huán))，所以for循環(huán)總共執(zhí)行了2m次，復雜度為Θ(2m)，所以總的復雜度為Θ(2m+n)1.1無向圖深度優(yōu)先搜索無向圖的邊根據(jù)深度優(yōu)先搜索可分成兩類1.1無向圖深度優(yōu)先搜索：例子1.1無向圖深度優(yōu)先搜索：例子1.1無向圖深度優(yōu)先搜索通過堆棧實現(xiàn)1.2有向圖深度優(yōu)先搜索有向圖的邊根據(jù)深度優(yōu)先搜索可分成兩類1.2有向圖深度優(yōu)先搜索：例子1.2有向圖深度優(yōu)先搜索：例子為何DFS用于無向圖時，不存在前向邊及橫跨邊?(1)前向邊（v，w）(2)橫跨邊（w,v）1.3深度優(yōu)先搜索：應用尋找圖的關節(jié)點顯然，如果G是連通的，那么在移除關節(jié)點和與其關聯(lián)的邊后，圖變?yōu)椴贿B通的1.3尋找圖的關節(jié)點用α(v)表示某一節(jié)點v自身的層級，用β(v)表示節(jié)點能夠到達的層級節(jié)點的α值可以直接用深度優(yōu)先搜索的先序號表示β值則由以下幾種情況決定:

1.3尋找圖的關節(jié)點根節(jié)點只要判斷其子節(jié)點的個數(shù)是否大于等于2即可非根節(jié)點：當要判斷某一個節(jié)點v是不是關節(jié)點，需要比較節(jié)點v的α值和其子節(jié)點的β值，只要任一子節(jié)點的β大于等于節(jié)點v的α值(說明這個子節(jié)點沒法到達比節(jié)點v更上層級)，則節(jié)點v為關節(jié)點，否則為非關節(jié)點1.3尋找圖的關節(jié)點Predfn用于計算\alpah值和\beta值rtdegree是深度優(yōu)先搜索樹根的度1.3尋找圖的關節(jié)點初始化節(jié)點v的alpha和beta為predfn依次訪問節(jié)點v的邊如果邊的另一個節(jié)點沒有訪問（樹邊），遞歸訪問，遞歸回來后，更新beta值，并判斷是否關節(jié)點如果邊的另一個節(jié)點已經(jīng)訪問（回邊），更新beta值1.3尋找圖的關節(jié)點a(1,1)，b(2,2)，c(3,3)，

d(4,4)，e(5,5)，

f(6,6)訪問efb,min{f.beta,b.alpha}=f(6,2)min{e.beta,f.beta}=e(5,2),d(4,2)，c(3,2),b(2,2)(b為關節(jié)點)g(7,7),h(8,8),i(9,9),j(10,10),k(11,11)k(11,9),j(10,9),i(9,9)(關節(jié)點),h(8,1)(關節(jié)點),h(7,1),a(1,1)decbaghijkf1.3圖的回路判斷問題：若G=(V,E)為一個有n個頂點和m條邊的有向或是無向圖。要測試G中是否包含有一個回路。方法：對G施加深度優(yōu)先搜索，如果探測到一個回邊，那么可以判定G中含有回路；否則G中無回路。注意：如果G是連通的無向圖，則不需要對G進行深度優(yōu)先搜索來判定是否有回路。G無回路，當且僅當|E|=|V|-1。1.3拓撲排序給定一個有向無回路圖(DirectedAcyclicGraph,DAG)G=(V,E)。拓撲排序是為了找到圖頂點的一個線性序，使得：如果(v,w)∈E,那么，在線性序中，v在w之前出現(xiàn)。我們假設在DAG中只有唯一一個入度為0的頂點；如果有一個以上的頂點入度為0，可以通過添加一個新的頂點s，然后將s指向所有入度為0的頂點，這樣s就成為唯一一個入度為0的頂點。decbafgabdcefg1.3拓撲排序拓撲排序的實現(xiàn)：從入度為0的頂點開始，對DAG實施深度優(yōu)先搜索。遍歷完成后，計數(shù)器postdfn恰好對應于一個在DAG中頂點的反拓撲序得到拓撲序：在DFS算法中恰當位置增加輸出語句，然后將輸出結果反轉。在DFS算法中恰當位置增加頂點入棧操作，然后依次取棧頂元素輸出。1.3拓撲排序decbafgdecbafgssdcbafge86735214abcedfg1.3

網(wǎng)絡頁面檢索深度優(yōu)先搜索是一種在開發(fā)爬蟲早期使用較多的方法優(yōu)點是能遍歷一個Web站點或深層嵌套的文檔集合；缺點是因為Web結構相當深,，有可能造成一旦進去，再也出不來的情況發(fā)生。主要內(nèi)容深度優(yōu)先搜索廣度優(yōu)先搜索單源最短路徑多源最短路徑2廣度優(yōu)先搜索2廣度優(yōu)先搜索v=2的BFS序列：21340遍歷過程結束3201432014BFS思路：距離初始頂點越近越優(yōu)先訪問！2廣度優(yōu)先搜索采用隊列Bfn表示訪問順序算法復雜度2.1無向圖廣度優(yōu)先搜索無向圖的邊根據(jù)深度優(yōu)先搜索可分成兩類2.1無向圖廣度優(yōu)先搜索：例子2.2有向圖廣度優(yōu)先搜索2.2有向圖廣度優(yōu)先搜索為什么有向圖的BFS中不會出現(xiàn)前向邊1.前向邊(Forwardedges)－在迄今為止所構建的搜索生成樹中，w是v的后裔，并且在探測(v,w)時，w已經(jīng)被標記為”visited”,則(v,w)為前向邊。2.既然要w是v的后裔，那么可以斷定，w所在層較v所在的層要低；另一方面，廣度優(yōu)先搜索生成樹是逐層產(chǎn)生的，即后裔頂點總是在祖先頂點之后訪問2.3有向圖廣度優(yōu)先搜索：應用假設目前需要對節(jié)點v的鄰節(jié)點實行入隊列，則這些要進入隊列的節(jié)點的最短距離(設w.dist)就是節(jié)點v的最短距離(設v.dist)加1，即w.dist=v.dist+1

算法復雜度主要內(nèi)容深度優(yōu)先搜索廣度優(yōu)先搜索單源最短路徑多源最短路徑3單源最短路徑3.1單源最短路徑：Dijkstra算法3.1單源最短路徑：Dijkstra算法在此算法中，設置兩個集合X和Y，其中X用于存放已經(jīng)加入到樹中的節(jié)點，Y用于存放還未加入到樹中的節(jié)點每個節(jié)點設置兩個屬性v.dist和v.prev

用于存放源節(jié)點到此節(jié)點的路徑長度(一旦此節(jié)點加入到樹中，此長度為最短距離)和此節(jié)點的在樹中的父節(jié)點(用于最短路徑計算)采用堆，復雜度為：3.1Dijkstra算法：例子3.1Dijkstra算法3.1Dijkstra算法3.1Dijkstra算法3.2Bellman-ford

算法當圖中存在權重為負的環(huán)時，某些點之間就不存在最短路徑，而Dijkstra算法是無法得出不存在最短路徑結果的Bellman-Ford算法當圖存在最短路徑，算法返回最短路徑，否則，返回false松弛操作

3.2Bellman-ford

算法3.2Bellman-ford

算法Bellman-Ford算法3.2Bellman-ford

算法算法中第一個for循環(huán)(語句4)共執(zhí)行了n?1次，嵌套內(nèi)的for循環(huán)(語句5，松弛操作)共執(zhí)行了m次，所以復雜度為O(nm)。第二個for循環(huán)(語句11)共執(zhí)行了m次?？倧碗s度為O(nm)3.2Bellman-ford

算法：例子3.2Bellman-ford

算法：例子3.3

SPFA

算法SPFA算法全稱是最短路徑快速算法(ShortestPathFasterAlgorithm)，它是對Bellman-Ford算法的改進在每輪松弛的過程中，我們保留那些d值更新過的節(jié)點，而在下一次松弛時，僅僅需要對這些節(jié)點為起始節(jié)點的邊進行松弛即可3.3SPFA

算法算法開始時，先將節(jié)點v0

進入隊列每次從隊列中取一個節(jié)點(語句6)，并對這個節(jié)點為起始節(jié)點的所有邊進行松弛在松弛的過程中，如果對應的節(jié)點d值發(fā)生改變，且節(jié)點并不在隊列中，則此節(jié)點進入隊列(語句8到11)節(jié)點進入隊列的次數(shù)達到n次，說明節(jié)點被松弛過n次，算法返回False，說明圖G存在權重為負的環(huán)。3.3SPFA

算法復雜度：SPFA算法在最壞的情況是和Bellman-Ford算法一樣的，也就是O(mn)。SPFA算法最好的情況為Ω(n)設圖為隨機圖形，則任意節(jié)點相連邊的條數(shù)的平均值為m/n(也就是算法for循環(huán)執(zhí)行m/n

次)，每個節(jié)點進入隊列的平均值為k次(k是一個常數(shù)，在稀疏圖中小于2)，即while循環(huán)執(zhí)行kn次，所以算法的平均復雜度為O(m/n?kn)=O(km)。3.4差分約束系統(tǒng)差分約束系統(tǒng)(systemofdifferenceconstraints)問題是對一組不等式求解的問題。其定義如下:給定n個變量和m個不等式，每個不等式形如xj?xi≤wk，其中0≤i,j<n,

0≤k<m，wk

已知，求x3.4差分約束系統(tǒng)轉換為：差分約束系統(tǒng)轉化成圖的形式，再通過求解最短路徑的方法(即通過松弛操作)就能夠實現(xiàn)差分系統(tǒng)的求解3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)是不是可以選擇任意一個節(jié)點作為源節(jié)點呢？在有向圖中并不是所有的節(jié)點都存在到其他節(jié)點的一條路徑，如例子中的v5

如果轉化后的圖是一個很復雜的圖，如何選擇一個源節(jié)點，其到其他所有節(jié)點都存在一條路徑?3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)主要內(nèi)容深度優(yōu)先搜索廣度優(yōu)先搜索單源最短路徑多源最短路徑4多源最短路徑多源最短路徑就是求圖中所有點對的最短路徑用Dijkstra算法對每個點求最短路徑Dijkstra算法的時間復雜度為O(n2)(采用堆的話，復雜度為O(mlogn))，用Dijkstra算法計算多源最短路徑，復雜度為O(n3)(或者O(mnlogn))4.1多源最短路徑：Floyd算法Floyd算法的主要思想是動態(tài)規(guī)劃，但因是求最短路徑，所以其本質也是松弛。4.1多源最短路徑：Floyd算法流程

通過矩陣實現(xiàn)上述操作4.1Floyd算法松弛過程例子4.1Floyd算法松弛過程松弛操作的流程是依次添加所有的節(jié)點，即v1，v2，v3，v4，并進行更新添加節(jié)點v1：如D0(4,2)=∞，通過節(jié)點v1

后，d4,2=D0(4,1)+D0(1,2)=5+4=9，所以d4,2

松弛為94.1Floyd算法松弛過程松弛操作的流程是依次添加所有的節(jié)點，即v1，v2，v3，v4，并進行更新添加節(jié)點v2：將D1

矩陣中的距離值和經(jīng)過節(jié)點v2

的距離值進行比較，如果經(jīng)過節(jié)點v2

的距離值小于D1

中的距離值，則進行距離更新4.1Floyd算法松弛過程松弛操作的流程是依次添加所有的節(jié)點，即v1，v2，v3，v4，并進行更新添加節(jié)點v3

4.1Floyd算法松弛過程松弛操作的流程是依次添加所有的節(jié)點，即v1，v2，v3，v4，并進行更新添加節(jié)點v4

4.1Floyd算法4.1Floyd算法動態(tài)規(guī)