《算法設(shè)計與分析》課件 第7章 圖算法

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

1.3尋找圖的關(guān)節(jié)點(diǎn)根節(jié)點(diǎn)只要判斷其子節(jié)點(diǎn)的個數(shù)是否大于等于2即可非根節(jié)點(diǎn)：當(dāng)要判斷某一個節(jié)點(diǎn)v是不是關(guān)節(jié)點(diǎn)，需要比較節(jié)點(diǎn)v的α值和其子節(jié)點(diǎn)的β值，只要任一子節(jié)點(diǎn)的β大于等于節(jié)點(diǎn)v的α值(說明這個子節(jié)點(diǎn)沒法到達(dá)比節(jié)點(diǎn)v更上層級)，則節(jié)點(diǎn)v為關(guān)節(jié)點(diǎn)，否則為非關(guān)節(jié)點(diǎn)1.3尋找圖的關(guān)節(jié)點(diǎn)Predfn用于計算\alpah值和\beta值rtdegree是深度優(yōu)先搜索樹根的度1.3尋找圖的關(guān)節(jié)點(diǎn)初始化節(jié)點(diǎn)v的alpha和beta為predfn依次訪問節(jié)點(diǎn)v的邊如果邊的另一個節(jié)點(diǎn)沒有訪問（樹邊），遞歸訪問，遞歸回來后，更新beta值，并判斷是否關(guān)節(jié)點(diǎn)如果邊的另一個節(jié)點(diǎn)已經(jīng)訪問（回邊），更新beta值1.3尋找圖的關(guān)節(jié)點(diǎn)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為關(guān)節(jié)點(diǎn))g(7,7),h(8,8),i(9,9),j(10,10),k(11,11)k(11,9),j(10,9),i(9,9)(關(guān)節(jié)點(diǎn)),h(8,1)(關(guān)節(jié)點(diǎn)),h(7,1),a(1,1)decbaghijkf1.3圖的回路判斷問題：若G=(V,E)為一個有n個頂點(diǎn)和m條邊的有向或是無向圖。要測試G中是否包含有一個回路。方法：對G施加深度優(yōu)先搜索，如果探測到一個回邊，那么可以判定G中含有回路；否則G中無回路。注意：如果G是連通的無向圖，則不需要對G進(jìn)行深度優(yōu)先搜索來判定是否有回路。G無回路，當(dāng)且僅當(dāng)|E|=|V|-1。1.3拓?fù)渑判蚪o定一個有向無回路圖(DirectedAcyclicGraph,DAG)G=(V,E)。拓?fù)渑判蚴菫榱苏业綀D頂點(diǎn)的一個線性序，使得：如果(v,w)∈E,那么，在線性序中，v在w之前出現(xiàn)。我們假設(shè)在DAG中只有唯一一個入度為0的頂點(diǎn)；如果有一個以上的頂點(diǎn)入度為0，可以通過添加一個新的頂點(diǎn)s，然后將s指向所有入度為0的頂點(diǎn)，這樣s就成為唯一一個入度為0的頂點(diǎn)。decbafgabdcefg1.3拓?fù)渑判蛲負(fù)渑判虻膶?shí)現(xiàn)：從入度為0的頂點(diǎn)開始，對DAG實(shí)施深度優(yōu)先搜索。遍歷完成后，計數(shù)器postdfn恰好對應(yīng)于一個在DAG中頂點(diǎn)的反拓?fù)湫虻玫酵負(fù)湫颍涸贒FS算法中恰當(dāng)位置增加輸出語句，然后將輸出結(jié)果反轉(zhuǎn)。在DFS算法中恰當(dāng)位置增加頂點(diǎn)入棧操作，然后依次取棧頂元素輸出。1.3拓?fù)渑判騞ecbafgdecbafgssdcbafge86735214abcedfg1.3

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

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

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

算法當(dāng)圖中存在權(quán)重為負(fù)的環(huán)時，某些點(diǎn)之間就不存在最短路徑，而Dijkstra算法是無法得出不存在最短路徑結(jié)果的Bellman-Ford算法當(dāng)圖存在最短路徑，算法返回最短路徑，否則，返回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次，所以復(fù)雜度為O(nm)。第二個for循環(huán)(語句11)共執(zhí)行了m次?？倧?fù)雜度為O(nm)3.2Bellman-ford

算法：例子3.2Bellman-ford

算法：例子3.3

SPFA

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

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

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

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

次)，每個節(jié)點(diǎn)進(jìn)入隊列的平均值為k次(k是一個常數(shù)，在稀疏圖中小于2)，即while循環(huán)執(zhí)行kn次，所以算法的平均復(fù)雜度為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)轉(zhuǎn)換為：差分約束系統(tǒng)轉(zhuǎn)化成圖的形式，再通過求解最短路徑的方法(即通過松弛操作)就能夠?qū)崿F(xiàn)差分系統(tǒng)的求解3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)3.4差分約束系統(tǒng)是不是可以選擇任意一個節(jié)點(diǎn)作為源節(jié)點(diǎn)呢？在有向圖中并不是所有的節(jié)點(diǎn)都存在到其他節(jié)點(diǎn)的一條路徑，如例子中的v5

如果轉(zhuǎn)化后的圖是一個很復(fù)雜的圖，如何選擇一個源節(jié)點(diǎn)，其到其他所有節(jié)點(diǎn)都存在一條路徑?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多源最短路徑多源最短路徑就是求圖中所有點(diǎn)對的最短路徑用Dijkstra算法對每個點(diǎn)求最短路徑Dijkstra算法的時間復(fù)雜度為O(n2)(采用堆的話，復(fù)雜度為O(mlogn))，用Dijkstra算法計算多源最短路徑，復(fù)雜度為O(n3)(或者O(mnlogn))4.1多源最短路徑：Floyd算法Floyd算法的主要思想是動態(tài)規(guī)劃，但因是求最短路徑，所以其本質(zhì)也是松弛。4.1多源最短路徑：Floyd算法流程

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

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

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

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

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

的距離值小于D1

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

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

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