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

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

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

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

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

算法當(dāng)圖中存在權(quán)重為負(fù)的環(huán)時(shí)，某些點(diǎn)之間就不存在最短路徑，而Dijkstra算法是無(wú)法得出不存在最短路徑結(jié)果的Bellman-Ford算法當(dāng)圖存在最短路徑，算法返回最短路徑，否則，返回false松弛操作

3.2Bellman-ford

算法3.2Bellman-ford

算法Bellman-Ford算法3.2Bellman-ford

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

算法：例子3.2Bellman-ford

算法：例子3.3

SPFA

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

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

進(jìn)入隊(duì)列每次從隊(duì)列中取一個(gè)節(jié)點(diǎn)(語(yǔ)句6)，并對(duì)這個(gè)節(jié)點(diǎn)為起始節(jié)點(diǎn)的所有邊進(jìn)行松弛在松弛的過(guò)程中，如果對(duì)應(yīng)的節(jié)點(diǎn)d值發(fā)生改變，且節(jié)點(diǎn)并不在隊(duì)列中，則此節(jié)點(diǎn)進(jìn)入隊(duì)列(語(yǔ)句8到11)節(jié)點(diǎn)進(jìn)入隊(duì)列的次數(shù)達(dá)到n次，說(shuō)明節(jié)點(diǎn)被松弛過(guò)n次，算法返回False，說(shuō)明圖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

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

0≤k<m，wk

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

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

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

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

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

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

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

的距離值小于D1

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

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

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