圖的基本算法

圖的基本算法第一頁，共五十七頁，編輯于2023年，星期二CompanyLogo

圖的一些基本概念及其表示Contents拓撲排序和歐拉回路問題最小生成樹和單源最短路問題二分圖匹配1234第二頁，共五十七頁，編輯于2023年，星期二CompanyLogo定義與術(shù)語圖：二元組<V,E>稱為圖(graph)。V為結(jié)點(node)點(vertex)集。

E為中結(jié)點之間的邊的集合。子圖：什么是子圖如果有兩個圖G和G’，G’的頂點集是G的頂點集的子集，且G’的邊集點對(u,v)稱為邊(edge)或稱弧(arc)，其中u,v屬于V，稱u,v是相鄰的(adjacent)，稱u,v與邊相關(guān)聯(lián)(incident)。連通圖：如果圖中任意一對頂點都有路徑存在，則稱該圖為連通的第三頁，共五十七頁，編輯于2023年，星期二CompanyLogo定義與術(shù)語若邊的點對(u,v)有序則稱為有向(directed)邊，其中u稱為頭(head)，v稱為尾(tail)。所形成的圖稱有向圖(directedgraph)。為對于u來說是出邊(outgoingarc)；對于v來說是入邊(incomingarc)。反之，若邊的點對無序則稱為無向(undirected)邊，所形成的圖稱無向圖(undirectedgraph)。第四頁，共五十七頁，編輯于2023年，星期二CompanyLogo定義與術(shù)語度(degree):一個頂點的度是指與該邊相關(guān)聯(lián)的邊的條數(shù)，頂點v的度記作deg(v)。無向圖：

有向圖：入度(indegree):在有向圖中，一個頂點v的入度是指與該邊相關(guān)聯(lián)的入邊(即邊的尾是v)的條數(shù)。出度(outdegree)：在有向圖中，一個頂點的出度是指與該邊相關(guān)聯(lián)的出邊(即邊的頭是v)的條數(shù)。路徑：如果從一個頂點v1出發(fā)，沿著一些邊依次經(jīng)過一些定點v2,v3……,vn,則稱頂點序列(v1,v2,…..,vn)為從頂點v1到vn的路徑?；芈罚喝绻粭l路徑上第一個頂點和最后一個頂點是相同的，則稱這樣的路徑為回路或環(huán)。第五頁，共五十七頁，編輯于2023年，星期二CompanyLogo圖的表示要表示一個圖G=(V,E),有兩種標(biāo)準的方法，即鄰接表和鄰接矩陣。這兩種方法即可以用于有向圖，也可以用于無向圖。第六頁，共五十七頁，編輯于2023年，星期二用鄰接表記錄圖

StructEdge { intdest;//記錄目的地 intvalue;//邊的權(quán)值 Edge*link;//記錄鏈表的下一個元素 }; Edge*edge=newEdge[n];//申請空間 for(inti=0;i<n;i++) edge[i]=NULL;Edge*L;While(cin>>u>>v)//(u,v)表示一條邊{ L=newEdge; L->dest=v;//填寫目的地 L->link=edge[u];//用新建的這條邊指向頂點u指向的鏈表 edge[u]=L;//再把L賦給edge[u]}CompanyLogo第七頁，共五十七頁，編輯于2023年，星期二遍歷鄰接表 for(inti=0;i<n;i++) { L=edge[i];//取得鄰接表的鏈表入口 while(L!=NULL)//輸出從頂點i出發(fā)可以到達的邊 { cout<<i<<“”<<L->dest<<endl; L=L->link;//取鏈表的下一個元素 } }CompanyLogo第八頁，共五十七頁，編輯于2023年，星期二CompanyLogoDFS，BFS拓撲排序強連通分支歐拉路徑和回路最小生成樹最短路徑哈密頓回路(NP)差分約束系統(tǒng)網(wǎng)絡(luò)流二分圖匹配圖論涉及到的問題和算法第九頁，共五十七頁，編輯于2023年，星期二CompanyLogo今天要講的問題最小生成樹最短路算法拓撲排序歐拉回路二分圖的匹配第十頁，共五十七頁，編輯于2023年，星期二拓撲排序拓撲排序是對有向無回路圖(DAG)頂點的一種排序，它使得如果存在u,v的有向路徑，那么滿足序中u在v前。拓撲排序就是由一種偏序(particalorder)得到一個全序(稱為拓撲有序(topologicalorder))。偏序是滿足自反性，反對稱性，傳遞性的序。一個圖的拓撲排序得到的結(jié)果可以看成是圖中所有頂點沿水平線排列而成的序列，而且所有的有向邊均是從左指向右在有向無回路圖用于說明事件發(fā)生的先后順序拓撲排序可以給出一個滿足時間先后的順序CompanyLogo第十一頁，共五十七頁，編輯于2023年，星期二陳熙大牛穿衣服的例子CompanyLogo第十二頁，共五十七頁，編輯于2023年，星期二拓撲排序算法描述拓撲排序的思路很簡單，就是每次任意找一個入度為0的點輸出，并把這個點以及與這個點相關(guān)的邊刪除。實際算法中，用一個隊列實現(xiàn)。算法： 1.把所有入度=0的點入隊Q。 2.若隊Q非空，則點u出隊，輸出u；否則轉(zhuǎn)4。 3.把所有與點u相關(guān)的邊(u,v)刪除，若此過程中有點v的入度變?yōu)?，則把v入隊Q，轉(zhuǎn)2。 4.若出隊點數(shù)<N，則說明有圈。

時間復(fù)雜度O(V+E)CompanyLogo第十三頁，共五十七頁，編輯于2023年，星期二歐拉回路歐拉回路，又稱“一筆畫”，是圖論中可行遍性問題的一種歐拉回路問題是圖論中最古老的問題之一。它誕生于十八世紀的歐洲古城哥尼斯堡。普瑞格爾河流經(jīng)這座城市，人們在兩岸以及河中間的兩個小島之間建了七座橋。市民們喜歡在這里散步，于是產(chǎn)生了這樣一個問題：是否可以找到一種方案，使得人們從自己家里出發(fā)，不重復(fù)地走遍每一座橋，然后回到家中？這個問題如果用數(shù)學(xué)語言來描述，就是在右圖中找出一條回路，使得它不重復(fù)地經(jīng)過每一條邊。這便是著名的“哥尼斯堡七橋問題”。CompanyLogo第十四頁，共五十七頁，編輯于2023年，星期二一些概念及定理歐拉回路:圖G中經(jīng)過每條邊一次并且僅一次的回路稱作歐拉回路。歐拉路徑:圖G中經(jīng)過每條邊一次并且僅一次的路徑稱作歐拉路徑。歐拉圖:存在歐拉回路的圖稱為歐拉圖。半歐拉圖存在歐拉路徑但不存在歐拉回路的圖稱為半歐拉圖。我們經(jīng)常需要判定一個圖是否為歐拉圖（或半歐拉圖），并且找出一條歐拉回路（或歐拉路徑）。對于無向圖有如下結(jié)論：定理1無向圖G為歐拉圖，當(dāng)且僅當(dāng)G為連通圖且所有頂點的度為偶數(shù)。CompanyLogo第十五頁，共五十七頁，編輯于2023年，星期二一些概念及定理推論1無向圖為半歐拉圖，當(dāng)且僅當(dāng)G為連通圖且除了兩個頂點的度為奇數(shù)之外，其它所有頂點的度為偶數(shù)。定理2有向圖為歐拉圖，當(dāng)且僅當(dāng)G的基圖連通，且所有頂點的入度等于出度。推論2有向圖為半歐拉圖，當(dāng)且僅當(dāng)G的基圖連通，且存在頂點的入度比出度大1、的入度比出度小1，其它所有頂點的入度等于出度。

基圖：忽略有向圖所有邊的方向，得到的無向圖稱為該有向圖的基圖。CompanyLogo第十六頁，共五十七頁，編輯于2023年，星期二歐拉回路算法描述由此可以得到以下求歐拉圖的歐拉回路的算法：在圖G中任意找一個回路；將圖G中屬于回路的邊刪除；在殘留圖的各極大連通子圖中分別尋找歐拉回路；將各極大連通子圖的歐拉回路合并到中得到圖的歐拉回路。CompanyLogo第十七頁，共五十七頁，編輯于2023年，星期二算法描述ProcedureEuler-circuit();BeginFor頂點start的每個鄰接點vDoIf邊(start,v)未被標(biāo)記ThenBegin

將邊(start,v)作上標(biāo)記;

將邊(v,start)作上標(biāo)記;Euler-circuit(v);

將邊(start,v)加入棧;End;End;最后依次取出棧S每一條邊而得到圖G的歐拉回路。由于該算法執(zhí)行過程中每條邊最多訪問兩次，因此該算法的時間復(fù)雜度為O(E)。CompanyLogo第十八頁，共五十七頁，編輯于2023年，星期二例題例題一單詞游戲題目描述有N個盤子，每個盤子上寫著一個僅由小寫字母組成的英文單詞。你需要給這些盤子安排一個合適的順序，使得相鄰兩個盤子中，前一個盤子上面單詞的末字母等于后一個盤子上面單詞的首字母。請你編寫一個程序，判斷是否能達到這一要求。如果能，請給出一個合適的順序。數(shù)據(jù)規(guī)模

N<=100000分析通過對題目條件的一些初步分析，我們很容易得到下面的模型。CompanyLogo第十九頁，共五十七頁，編輯于2023年，星期二分析模型1：以N個盤子作為頂點；如果盤子A的末字母等于盤子B的首字母，那么從A向B連一條有向邊。對于樣例我們可以按下圖所示的方式構(gòu)圖。這樣，問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過每一個頂點的路徑，即哈密爾頓路。然而，求哈密爾頓路是一個十分困難的問題，這樣的模型沒有給我們的解題帶來任何便利。因此，我們必須另辟蹊徑。CompanyLogo第二十頁，共五十七頁，編輯于2023年，星期二分析模型2：經(jīng)過分析，我們發(fā)現(xiàn)模型1的失敗之處在于，圖中需要遍歷的信息——也就是每一個盤子——表示在頂點上，而頂點的遍歷問題不易解決。能否將遍歷信息表示在邊上呢？考慮如下的構(gòu)圖方法：以26個字母作為頂點；對于每一個盤子，如果它的首字母為c1，末字母為c2，那么從c1向c2連一條有向邊。對于樣例我們可以按下圖所示的方式構(gòu)圖這樣，問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過每一條邊的路徑，即歐拉路徑。這個問題能夠在O(E)時間內(nèi)解決。CompanyLogo第二十一頁，共五十七頁，編輯于2023年，星期二最小生成樹在電路設(shè)計中，常常需要把一些電子元件的插腳用電線連接起來。如果每根電線連接兩個插腳，把所有n個插腳連接起來，只要用n-1根電線就可以了。在所有的連接方案中，我們通常對電線總長度最小的連接方案感興趣。把問題轉(zhuǎn)化為圖論模型就是：一個無向連通圖G=(V,E)，V是插腳的集合，E是插腳兩兩之間所有可能的連接的集合。給每條邊(u,v)一個權(quán)值w(u,v)，表示連接它們所需的電線長度。我們的目標(biāo)就是找到一個無環(huán)的邊集T，連接其中所有的點且使總權(quán)值最小。既然T是連接所有點的無環(huán)邊集，它一定是一棵樹。因為這棵樹是從圖G中生成出來的，我們把它叫做生成樹。如果一棵生成樹在所有生成樹中總權(quán)值最小，我們就把它稱作最小生成樹。CompanyLogo第二十二頁，共五十七頁，編輯于2023年，星期二KruskalMST-KRUSKAL(G,w)1.A←Ф2.for每個結(jié)點v∈V[G]3.doMAKE-SET(v)4.根據(jù)權(quán)w的非遞減順序?qū)的邊進行排序5.for每條邊(u,v)∈E，按權(quán)的非遞減次序6.doifFIND-SET(u)≠FIND-SET(v)7.thenA←A∪{(u,v)}8.UNION(u,v)9.returnA復(fù)雜度E*lgECompanyLogo第二十三頁，共五十七頁，編輯于2023年，星期二步驟CompanyLogo第二十四頁，共五十七頁，編輯于2023年，星期二步驟CompanyLogo第二十五頁，共五十七頁，編輯于2023年，星期二步驟CompanyLogo第二十六頁，共五十七頁，編輯于2023年，星期二步驟CompanyLogo第二十七頁，共五十七頁，編輯于2023年，星期二Prim算法Kruskal找出連接任意兩棵樹的所有邊中，具有最小權(quán)值的邊(u,v)，把它添加到正在生長的森林中。Prim的特點它一直維持生成單棵樹，而Kruskal生成時可以存在多個樹。Prim每次選一個點加入到集合中，直到把所有點都加入到集合中CompanyLogo第二十八頁，共五十七頁，編輯于2023年，星期二算法描述MST-PRIM(G,w,r)1.Q←V[G]2.for每個u∈Q3.dokey[u]←∞4.key[r]←05.π[r]←NIL6.whileQ<>Ф7.dou←EXTRACT-MIN(Q){返回隊列Q中最小的元素}8.for每個v∈Adj[u]9.doifv∈Qandw(u,v)<key[v]10.thenπ[v]←u11.key[v]←w(u,v)CompanyLogo第二十九頁，共五十七頁，編輯于2023年，星期二執(zhí)行過程CompanyLogo第三十頁，共五十七頁，編輯于2023年，星期二執(zhí)行過程CompanyLogo第三十一頁，共五十七頁，編輯于2023年，星期二執(zhí)行過程CompanyLogo第三十二頁，共五十七頁，編輯于2023年，星期二最短路概述最短路問題是圖論中的核心問題之一，它是許多更深層算法的基礎(chǔ)。同時，該問題有著大量的生產(chǎn)實際的背景。不少問題從表面上看與最短路問題沒有什么關(guān)系，卻也可以歸結(jié)為最短路問題乘汽車旅行的人總希望找出到目的地盡可能短的行程。如果有一張地圖并在地圖上標(biāo)出了每對十字路口之間的距離，如何找出這一最短行程？在乘車旅行的例子中，我們可以把公路地圖模型化為一個圖：結(jié)點表示路口，邊表示連接兩個路口的公路，邊權(quán)表示公路的長度。我們的目標(biāo)是從起點出發(fā)找一條到達目的地的最短路徑。CompanyLogo第三十三頁，共五十七頁，編輯于2023年，星期二最短路概述我們一般所將的都是單源最短路徑問題，即我們希望找出從某給定點s到每個頂點的最短路徑。不過有許多其他的問題也可以用最短路算法解決單目標(biāo)最短路徑問題：找出從每一結(jié)點v到某指定結(jié)點u的一條最短路徑。把圖中的每條邊反向，我們就可以把這一問題轉(zhuǎn)化為單源最短路徑問題。單對結(jié)點間的最短路徑問題：對于某給定結(jié)點u和v，找出從u到v的一條最短路徑。如果我們解決了源結(jié)點為u的單源問題，則這一問題也就獲得了解決每對結(jié)點間的最短路徑問題：對于每對結(jié)點u和v，找出從u到v的最短路徑。我們可以用單源算法對每個結(jié)點作為源點運行一次就可以解決問題。CompanyLogo第三十四頁，共五十七頁，編輯于2023年，星期二最短路涉及到的問題負權(quán)邊值：在某些最短路的實例中，可能存在權(quán)值為負的邊。如果存在一條從s可達的負權(quán)回路，那么最短路的權(quán)的定義就不能存在了。因為只要穿越負權(quán)回路任意次我們就可以發(fā)現(xiàn)從s到e可以無限變小。CompanyLogo第三十五頁，共五十七頁，編輯于2023年，星期二最短路涉及到的問題回路：一條最短路徑能包含回路嗎？它不能包含負權(quán)回路。它也不會包含正權(quán)回路，因為從路徑上移去回路后回路后可以產(chǎn)生一個具有相同源點和終點，權(quán)值更小的路徑。CompanyLogo第三十六頁，共五十七頁，編輯于2023年，星期二松弛技術(shù)對于每個頂點v,都設(shè)置了一個屬性d[v],用來描述從源點s到v的最短路的上界，稱為最短路徑估計。init(){ for(inti=0;i<n;i++) d[i]=∞; d[s]=0}Relax(u,v,w){ If(d[v]>d[u]+w) d[v]=d[u]+w; pre[v]=u;}三角不等式：對于任意邊(u,v)，有δ(s,v)≤δ(s,u)+w(u,v).CompanyLogo第三十七頁，共五十七頁，編輯于2023年，星期二CompanyLogo最短路算法DijkstraSPFABellmanFord最短路算法第三十八頁，共五十七頁，編輯于2023年，星期二最短路算法我們著重討論兩種常用算法：Dijkstra算法和Bellman-Ford算法。雖然它們都是建立在松弛技術(shù)基礎(chǔ)上的算法，但是在實現(xiàn)上有著各自的特點，適用的范圍也有所不同。另外，我們還將介紹一種期望復(fù)雜度與邊數(shù)同階的高效算法——SPFA算法，并對其復(fù)雜度作出簡要的分析。CompanyLogo第三十九頁，共五十七頁，編輯于2023年，星期二DijkstraDijkstra算法解決了有向加權(quán)圖的最短路徑問題，該算法的條件是該圖所有邊的權(quán)值非負，因此在本小節(jié)我們約定：對于每條邊(u,v)E，w(u,v)>=0。Dijkstra算法中設(shè)置了一結(jié)點集合S，從源結(jié)點s到集合S中結(jié)點的最終最短路徑的權(quán)均已確定，即對所有結(jié)點v屬于S，有d[v]已經(jīng)為最小。算法反復(fù)挑選出其最短路徑估計為最小的結(jié)點u屬于V-S，把u插入集合S中，并對離開u的所有邊進行松弛CompanyLogo第四十頁，共五十七頁，編輯于2023年，星期二Dijkstra算法描述Dijkstra(G,w,s)INIT(G,S)S=NULLQ=V[G]WhileQDou=EXTRACT-MIN(Q)S=SU{u}For每個頂點vAdj[u]DoRELAX(u,v,w)CompanyLogo第四十一頁，共五十七頁，編輯于2023年，星期二算法執(zhí)行過程CompanyLogo第四十二頁，共五十七頁，編輯于2023年，星期二Bellman-Ford

Bellman-Ford算法Bellman-Ford算法能在更一般的情況下解決單源點最短路徑問題，在該算法下邊的權(quán)可以為負。正如Dijkstra算法一樣，Bellman-Ford算法運用了松弛技術(shù)，對每一結(jié)點v，逐步減小從源s到v的最短路徑的估計值d[v]直至其達到實際最短路徑的權(quán)

(s,v)，如果圖中存在負權(quán)回路，算法將會報告最短路不存在。Bellman-Ford算法可以用于解決差分約束系統(tǒng)CompanyLogo第四十三頁，共五十七頁，編輯于2023年，星期二算法描述Bellman-Ford(G,w,s)init(G,s)Fori1to|V[G]|-1DoFor每條邊(u,v)E[G]DoRELAX(u,v,w)For每條邊(u,v)E[G]DoIfd[v]>d[u]+w(u,v)ThenReturnFALSEReturnTRUE時間復(fù)雜度為O(V*E);CompanyLogo第四十四頁，共五十七頁，編輯于2023年，星期二執(zhí)行過程CompanyLogo第四十五頁，共五十七頁，編輯于2023年，星期二Bellman-Ford思想Bellman-Ford算法的思想基于以下事實：“兩點間如果有最短路，那么每個結(jié)點最多經(jīng)過一次。也就是說，這條路不超過n-1條邊?！保ㄈ绻粋€結(jié)點經(jīng)過了兩次，那么我們走了一個圈。如果這個圈的權(quán)為正，顯然不劃算；如果是負圈，那么最短路不存在；如果是零圈，去掉不影響最優(yōu)值）根據(jù)最短路的最優(yōu)子結(jié)構(gòu)，路徑邊數(shù)上限為k時的最短路可以由邊數(shù)上限為k-1時的最短路“加一條邊”來求，而根據(jù)剛才的結(jié)論，最多只需要迭代n-1次就可以求出最短路。CompanyLogo第四十六頁，共五十七頁，編輯于2023年，星期二SPFAShortest

path

faster

algorithmSPFA其實就是Bellman-Ford的一種隊列實現(xiàn)，減少了冗余，即松馳的邊至少不會以一個d為∞的點為起點。算法：1.隊列Q={s}，，2.取出隊頭u,枚舉所有的u的臨邊.若d(v)>d(u)+w(u,v)則改進，pre(v)=u，由于d(v)減少了，v可能在以后改進其他的點，所以若v不在Q中，則將v入隊。3.一直迭代2，直到隊列Q為空(正常結(jié)束)，或有的點的入隊次數(shù)>=n（含有負圈）。CompanyLogo第四十七頁，共五十七頁，編輯于2023年，星期二SPFA算法分析一般用于找負圈(效率高于Bellman-Ford)，稀疏圖的最短路由于點可能多次入隊，但隊列中同時不會超過n個點。所以用一個長度為n的循環(huán)隊列來實現(xiàn)這個隊。SPFA在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復(fù)迭代下去。設(shè)一個點用來作為迭代點對其它點進行改進的平均次數(shù)為k，有辦法證明對于通常的（不含負圈，較稀疏）情況，k在2左右。算法復(fù)雜度理論上同Bellman-Ford，O(nm)，但實際上卻是O(km)。

CompanyLogo第四十八頁，共五十七頁，編輯于2023年，星期二例題例題1——貨幣兌換（pku1860|zju1544）若干個貨幣兌換點在我們的城市中工作著。每個兌換點只能進行兩種指定貨幣的兌換。不同兌換點兌換的貨幣有可能相同。每個兌換點有它自己的兌換匯率，貨幣A到貨幣B的匯率表示要多少單位的貨幣B才能兌換到一個單位的貨幣A。當(dāng)然貨幣兌換要支付一定量的中轉(zhuǎn)費。例如，如果你想將100美元兌換成俄元，匯率是29.75，中轉(zhuǎn)費為0.39，那么你會兌換到(100-0.39)×29.75=2963.3975俄元。CompanyLogo第四十九頁，共五十七頁，編輯于2023年，星期二例題城市中流通著N(N<=100)類貨幣，用數(shù)字1至N標(biāo)號表示。每個貨幣兌換點用6個數(shù)字來描述：整數(shù)A和B是兌換貨幣的編號，實數(shù)RAB，CAB，RBA，CBA分別是A兌換成B和B兌換成A的匯率和中轉(zhuǎn)費用。Nick有一些第S類貨幣，他想在若干次交換后增加他的資金，當(dāng)然這些資金最終仍是第S類貨幣。請你告訴他該想法能否實現(xiàn)SampleInput

32120.0//貨幣數(shù)量,兌換點數(shù)量,初始貨幣編號資金

121.001.001.001.00//A,B,Rab,Rba,Cab,Cba 231.101.001.101.00SampleOutput YESCompanyLogo第五十頁，共五十七頁，編輯于2023年，星期二分析如果我們可以求出，通過一系列的兌換

每種貨幣可以得到的最大值，那么問題便迎刃而解了。因為要是可以得到的第S類貨幣最大值都不比初值大，資金肯定無法增加；否則，得到最大值的過程就是一種解法。到了這里，我們發(fā)現(xiàn)求最大值和我們學(xué)過的求最短路很類似，構(gòu)圖用最短路算法做也顯得水到渠成了。具體做法是：將N種貨幣看成N個結(jié)點，將每個兌換點轉(zhuǎn)化為兩條有向邊。根據(jù)兌換公式，目前從A貨幣兌換到B貨幣的匯率和中轉(zhuǎn)費用為RAB，CAB，那么由對應(yīng)的A結(jié)點向B結(jié)點連一條有向邊，從A點得到的B的可能最大值為：(A目前的最大值-CAB)×RAB。CompanyLogo第五十一頁，共五十七頁，編輯于2023年，星期二分析注意，這里所求的是最大值，為了轉(zhuǎn)化為最短路，我們可以在數(shù)字前面加上一個負號。更簡潔的方法是利用求最短路