湘潭大學數(shù)據(jù)結(jié)構(gòu)課件Ch09Graph講義

第9章圖論算法介紹幾個現(xiàn)實生活中發(fā)生的問題，可以轉(zhuǎn)化成圖論算法；解決幾個普通的圖論問題的算法；深度優(yōu)先搜索(depth-firstsearch)技巧；……【例】圖中村與村之間的道路是一個較長遠的規(guī)劃目標。§0引子最小生成樹問題9.5節(jié)討論[問題1]公路村村通項目要求用最小的投入實現(xiàn)每個村都能夠有公路通達。那么應該選擇建設哪些道路可以使這個投資最小呢？（假設每條道路的建設成本已知）【例】下圖為公路規(guī)劃抽象及造價預算示例圖?！?引子[問題2]在同樣的抽象圖中，假設把“造價”的含義修改成“距離”，那么我們就可以問：要走遍每個村莊，并回到起點，該如何走才能夠使得總的路程最短？88756655444532745BCDFLHWXYZ巡回售貨員問題（TSP）P.253討論

通常：用|V|表示頂點的數(shù)量（|V|≥1），用|E|表示邊的數(shù)量（|E|≥0）。[例]上圖給出了一個圖的示例，在該圖中：集合V＝

，|V|=；集合E＝

|E|=“圖”

G可以表示為集合：G=（V,E）。每條邊是一個頂點對（v,w）

E，并且v,w

V。

圖的定義88756655444532745BCDFLHWXYZ§1若干定義{B，C，D，F(xiàn)，H，L，W，X，Y，Z}10{(Z,B)，(Z,W)，(B,W)，(B,L)，(B,D)，(D,L)，(W,X)，(W,L)，(L,H)，(L,F)，(X,H)，(X,Y)，(H,Y)，(H,F)，(H,C)，(F,C)，(Y,C)}17。(1)無向圖（UndirectedGraphs）:邊（v,w）等同于邊（w,v）。用圓括號“（）”表示無向邊。(a)無向圖G1

1230G1=(V1，E1)，V1={0，1，2，3}，E1={（0,1）,（0,2）,（0,3）,（2,3）}?！?若干定義(b)有向圖G2

12304(2)有向圖（DirectedGraphs）:邊<v,w>不同于邊<w,v>。用尖括號“<>”表示有向邊；有向邊也稱“弧（Arc）”。G2=(V2，E2)，V2={0，1，2，3，4}，E2={<1,0>,<2,0>，<0,2>，<2,1>，<4,2>，<1,3>，<3,4>}?！?若干定義(3)簡單圖（SimpleGraphs）:沒有重邊和自回路的圖。1201230(a)重邊圖(b)自回路圖

本書只討論簡單圖?！?若干定義(5)路徑、簡單路徑、回路、無環(huán)圖(4)鄰接點:如果（v,w）或<v,w>是圖中任意一條邊，那么稱v和w互為“鄰接點（AdjacentVertices）”。

圖G中從vp

到vq

的路徑::={vp,vi1,vi2,,vin,vq}使得(vp,vi1),(vi1,vi2),,(vin,vq)或<vp,vi1>,,<vin,vq>都屬于E(G)

路徑長度::=路徑中邊的數(shù)量

簡單路徑::=vi1,vi2,,vin

都是不同頂點

回路

::=起點和終點相同（vp

=vq

）的路徑

無環(huán)圖

::=不存在任何回路的圖

有向無環(huán)圖

::=不存在回路的有向圖，也稱DAG（DirectedAcyclicGraph）§1若干定義(7)有向完全圖：在頂點數(shù)給定為n的情況下，有向邊數(shù)達到最大的n(n-1)條邊。(6)無向完全圖：在頂點數(shù)給定為n的情況下，邊數(shù)達到最大的n(n-1)/2條邊。（因為沒有重邊和自回路邊）02130213(8)頂點的度(degree)、入度(in-degree)、出度(out-degree)：

度(v)::=與頂點v相關的邊數(shù)v入度(v)=3;出度(v)=1;度(v)=4

給定

n

個頂點和e

條邊的圖G,

則有:§1若干定義(10)權(quán)（Cost）、網(wǎng)絡（Network）(9)稠密圖、稀疏圖：是否滿足|E|>|V|log2|V|，作為稠密圖和稀疏圖的分界條件。(12)無向圖的頂點連通、連通圖、連通分量：(11)圖G的子圖G’：V(G’)V(G)&&E(G’)E(G)

如果無向圖從一個頂點vi到另一個頂點vj(i≠j)有路徑，則稱頂點vi和vj是“連通的（Connected）”

無向圖中任意兩頂點都是連通的，則稱該圖是“連通圖（ConnectedGraph）”。

無向圖的極大連通子圖稱為“連通分量（ConnectedComponent）”。連通分量的概念包含以下4個要點：

子圖、連通、極大頂點數(shù)、極大邊數(shù)§1若干定義(13)有向圖的強連通圖、連通分量：

有向圖中任意一對頂點vi

和vj(i≠j)均既有從vi到vj的路徑，也有從vj到vi的路徑，則稱該有向圖是“強連通圖（StronglyConnectedGraph）”。

有向圖的極大強連通子圖稱為“強連通分量（StronglyConnectedComponent）”。連通分量的概念也包含前面4個要點。(14)樹、生成樹：

樹是圖的特例：無環(huán)的無向圖。所謂連通圖G的“生成樹（SpanningTree）”，是G的包含其全部n個頂點的一個極小連通子圖。它必定包含且僅包含G的n-1條邊。生成樹有可能不唯一。當且僅當G滿足下面4個條件之一（完全等價）：①G有n-1條邊，且沒有環(huán)；②G有n-1條邊，且是連通的；③G中的每一對頂點有且只有一條路徑相連；④G是連通的，但刪除任何一條邊就會使它不連通?！?若干定義類型名稱：圖（Graph）操作集：對于任意的圖G

Graph，頂點v、v1和v2

ertex，以及任一訪問頂點的函數(shù)visit()，操作舉例：數(shù)據(jù)對象集：一非空的頂點集合Vertex和一個邊集合Edge，每條邊用對應的一對頂點表示。

GraphCreate()：構(gòu)造并返回一個空圖；

voidDestroy(GraphG)：釋放圖G占用的存儲空間；

GraphInsertVertex(GraphG,Vertexv)：返回一個在G中增加了新頂點v的圖

GraphInsertEdge(GraphG,Vertexv1,Vertexv2)：返回一個在G中增加了新邊(v1,v2)的圖；GraphDeleteVertex(GraphG,Vertexv)：刪除G中頂點v及其相關邊，將結(jié)果圖返回；

GraphDFS（GraphG,Vertexv,visit()）：在圖G中，從頂點v出發(fā)進行深度優(yōu)先遍歷；……§1若干定義鄰接矩陣（AdjacencyMatrix）

邊的信息：用鄰接矩陣A[n][n]表示為:3V0V3V2V1

圖的鄰接矩陣表示示例圖的鄰接矩陣表示示例

圖的表示

頂點信息：有n個頂點的圖G(V,E)用一維數(shù)組D[n]表示；§1.1圖的表示鄰接矩陣

特點：

無向圖的鄰接矩陣一定是一個對稱矩陣。所需存儲元素的個數(shù)是|V|×(|V|-1)/2。

對于無向圖，鄰接矩陣的第i行（或第i列）非0元素（或非∞元素）的個數(shù)正好是第i個頂點的度Degree(vi)。

對于有向圖，鄰接矩陣的第i行（或第i列）非0元素的個數(shù)正好是第i個頂點的出度(vi)（或入度(vi)）。

存儲空間代價為Θ(|V|2)。要確定圖中有多少條邊，所花費的時間代價也是Θ(|V|2)。對稀疏圖來說，這樣的代價明顯是不合理的！§1.1圖的表示鄰接表(AdjacencyList)

對于圖G中的每個頂點vi，將所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，再將所有點的鄰接表表頭放到一個數(shù)組中，就構(gòu)成了圖的鄰接表。

無向圖的鄰接表表示示例VertexFirstEdge頂點域

邊表頭指針AdjVNext鄰接點域

指針域3V0V3V2V1§1.1圖的表示鄰接表與逆鄰接表

無向圖中有n個頂點和e條邊，則它的鄰接表需n個頭結(jié)點和2e個表邊結(jié)點。顯然，在邊稀疏

(e<<n(n-1)/2)的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間；

無向圖的鄰接表，頂點vi的度恰為第i個鏈表中的結(jié)點數(shù)；而在有向圖中，第i個鏈表中的結(jié)點個數(shù)只是頂點vi的出度，為便于確定頂點vi的入度，可以建立一個有向圖的逆鄰接表，即對每個頂點vi

建立一個鏈接以vi為頭的弧的鏈表。例如：§1.1圖的表示§2拓撲排序〖例〗

獲得一個計算機科學學位所需的課程。怎么把這個表轉(zhuǎn)換成圖表示?§2拓撲排序AOV網(wǎng)::=圖G中V(G)表示活動（如：課程），E(G)表示優(yōu)先關系(如

表示C1是C3的先修課程)。C1C3

i

是j

的前驅(qū)::=從i

到

j有一條路徑

i是j

的直接前驅(qū)::=<i,j>E(G)

所以

j

稱為i的后繼(直接后繼)

偏序::=一種優(yōu)先關系，同時具有傳遞性(i

k,k

j

i

j)和

非自反性(i

i

是不可能的).可行的AOV網(wǎng)必定是一個dag(directedacyclicgraph，有向無環(huán)圖).Note:

如果優(yōu)先關系是自反的，那么必定有一個

i

存在，使得

i

是i的前驅(qū)。那就是說，

i

必須在i

開始之前被完成（顯然不合理）。因此如果一個項目是可行的，

它必然是非自反的?！?拓撲排序【定義】拓撲排序是圖中頂點的一個線性排序，它使得對任意兩個頂點

i,j,如果i

是

j

的一個前驅(qū)，那么在排序中i

出現(xiàn)在

j

的前面?！祭?/p>

一個可能的計算機科學學位課程學習表順序如下：試著用AOV圖表示出來求出給定DAG的一個拓撲序列，相當于進行一個作業(yè)調(diào)度。如何來求一個拓撲序列呢？簡單算法：[step1]如果找得到任何一個入度為0的頂點v，則step2，否則step4；[step2]輸出頂點v，并從圖中刪除該頂點以及與其相連的所有邊；[step3]對改變后的圖重復這一過程，轉(zhuǎn)step1；[step4]如果已經(jīng)輸出全部頂點，則結(jié)束；否則該有向圖不是DAG。

理論依據(jù)是基于下面的結(jié)論：一個頂點數(shù)|V|>1的有向圖，如果每個頂點的入度都大于0，那么它必定存在回路。§2拓撲排序Note:對一個圖來說，拓撲排序不是唯一的。如，要達到獲得計算機科學學位的條件有幾種途徑（拓撲排序）。Goal測試一個AOV的可行性，可能的話生成一個拓撲排序。voidTopsort(GraphG){intCounter;VertexV,W;

for(Counter=0;Counter<NumVertex;Counter++){ V=FindNewVertexOfDegreeZero();

if(V==NotAVertex){ Error(“Graphhasacycle”);break;} TopNum[V]=Counter;/*oroutputV*/

for(eachWadjacenttoV) Indegree[W]––;}}/*O(|V|)*/

T=O(|V|2)檢查整個InDegree數(shù)組，所需時間是O(|V|)，此函數(shù)被調(diào)用|V|次，故本算法的時間復雜性為

O(|V|2)§2拓撲排序

實現(xiàn):

將所有度為0的未標記頂點放在一個特殊的盒子里（隊列或棧）。v1v2v6v7v3v4v5voidTopsort(GraphG){QueueQ;

intCounter=0;VertexV,W;Q=CreateQueue(NumVertex);MakeEmpty(Q);

for(eachvertexV)

if(Indegree[V]==0)Enqueue(V,Q);

while(!IsEmpty(Q)){ V=Dequeue(Q); TopNum[V]=++Counter;/*assignnext*/

for(eachWadjacenttoV)

if(––Indegree[W]==0)Enqueue(W,Q);}/*end-while*/

if(Counter!=NumVertex) Error(“Graphhasacycle”);DisposeQueue(Q);/*freememory*/}0v1Indegree1v22v33v41v53v62v7v10v21210v50v41v60v320v710T=O(|V|+|E|)MistakesinFig9.4【例】交通的最短路徑選擇。最短路徑有不同含義?！?最短路徑算法給定一個圖G=(V,E),以及權(quán)值方程

c(e)，e

E(G)。

從源點到目標點的路徑P

的長度是(也稱帶權(quán)路徑長)。1.單源最短路徑問題給定一個帶權(quán)圖

G=(V,E),以及一個指定頂點s,找到從s

到圖G其他所有頂點的最短帶權(quán)路徑。v1v2v6v7v3v4v52421310258461v1v2v6v7v3v4v524213–10258461負值回路Note:如果沒有負值回路，從s到s

的最短路徑定義為0?！?最短路徑算法

無權(quán)最短路徑v1v2v6v7v3v4v500:

v31:

v1andv6112:

v2andv4223:

v5andv733

算法梗概廣度優(yōu)先搜索

實現(xiàn)Table[i].Dist::=distancefromstovi

/*initializedtobeexceptfors*/Table[i].Known::=1ifviischecked;or0ifnotTable[i].Path::=fortrackingthepath/*initializedtobe0*/§3最短路徑算法voidUnweighted(TableT){intCurrDist;VertexV,W;

for(CurrDist=0;CurrDist<NumVertex;CurrDist++){

for(eachvertexV)

if(!T[V].Known&&T[V].Dist==CurrDist){ T[V].Known=true;

for(eachWadjacenttoV)

if(T[W].Dist==Infinity){ T[W].Dist=CurrDist+1; T[W].Path=V; }/*end-ifDist==Infinity*/ }/*end-if!Known&&Dist==CurrDist*/}/*end-forCurrDist*/}Theworstcase:v1v2v6v7v3v4v5v9v8

T=O(|V|2)如果

V

未標記，但Dist<Infinity,那么

Dist

既不是CurrDist也不是CurrDist+1.§3最短路徑算法

改進算法voidUnweighted(TableT){/*TisinitializedwiththesourcevertexSgiven*/QueueQ;VertexV,W;Q=CreateQueue(NumVertex);MakeEmpty(Q);Enqueue(S,Q);/*Enqueuethesourcevertex*/

while(!IsEmpty(Q)){V=Dequeue(Q);T[V].Known=true;/*notreallynecessary*/

for(eachWadjacenttoV)

if(T[W].Dist==Infinity){ T[W].Dist=T[V].Dist+1; T[W].Path=V; Enqueue(W,Q); }/*end-ifDist==Infinity*/}/*end-while*/

DisposeQueue(Q);/*freememory*/}v1v2v6v7v3v4v50

v1Dist

Path

v20v3

v4

v5

v6

v70000000v3v71v3v11v3v61122v1v222v1v433v2v533v4T=O(|V|+|E|)

為什么?如果不是這樣，那么這條路徑上必然存在頂點w不在S

中。那么...§3最短路徑算法

Dijkstra算法(帶權(quán)最短路徑算法)令

S={s

與已經(jīng)找到最短路徑的頂點

vi}對任意

u

S,定義

distance[u]=最小長度路徑{s

(vi

S)u}。如果路徑都是按非降序生成的，那么

最短路徑必然只經(jīng)過

vi

S;

當distance[u]=min{w

S|distance[w]}，

(如果

u

不是唯一的，那么我們可在其中任選一頂點);/*貪心策略*/u

被選中

如果

distance[u1]<distance[u2]

，并且

u1

被加入

S,那么

distance[u2]

可能會變化。如果是這樣，從

s

到

u2

的一條更短的路徑必定經(jīng)過

u1

，且

distance’[u2]=distance[u1]+length(<u1,u2>).§3最短路徑算法voidDijkstra(TableT){/*TisinitializedbyFigure9.30onp.303*/VertexV,W;for(;;){V=smallestunknowndistancevertex;if(V==NotAVertex) break;T[V].Known=true;

for(eachWadjacenttoV)

if(!T[W].Known)

if(T[V].Dist+Cvw<T[W].Dist){ Decrease(T[W].Distto T[V].Dist+Cvw); T[W].Path=V; }/*end-ifupdateW*/}/*end-for(;;)*/}v1v2v6v7v3v4v524213102584610v1DistPath

v2

v3

v4

v5

v6

v700000002v11v13v43v49v45v48v36v7/*notworkforedgewithnegativecost*/圖9.31實現(xiàn)了打印路徑的例程。/*O(|V|)*/§3最短路徑算法

實現(xiàn)1V=最小的未知距離頂點；/*簡單地掃描表–O(|V|)*/T=O(|V|2+|E|)如果圖是稠密的，這種方法較好

實現(xiàn)2V=最小的未知距離頂點;/*將distances放在優(yōu)先隊列里，并調(diào)用DeleteMin–O(log|V|)*/Decrease(T[W].DisttoT[V].Dist+Cvw);/*方法1:DecreaseKey–O(log|V|)*/T=O(|V|log|V|+|E|log|V|)=O(|E|log|V|)/*方法2:插入W已更新的Dist到優(yōu)先隊列*//*必須連續(xù)執(zhí)行DeleteMin知道一個未知頂點出現(xiàn)*/如果圖是稀疏的，這種方法較好T=O(|E|log|V|)但要求|E|次DeleteMin及|E|的空間。

其他改進:配對堆(Ch.12)與Fibonacci堆(Ch.11)§3最短路徑算法

具有負值邊的圖HeyIhaveagoodidea:whydon’twesimplyaddaconstanttoeachedgeandthusremovenegativeedges?Toosimple,andna?ve…Trythisoneout:

13422–221voidWeightedNegative(TableT){/*TisinitializedbyFigure9.30onp.303*/QueueQ;VertexV,W;

Q=CreateQueue(NumVertex);MakeEmpty(Q);Enqueue(S,Q);/*Enqueuethesourcevertex*/

while(!IsEmpty(Q)){V=Dequeue(Q);for(eachWadjacenttoV)

if(T[V].Dist+Cvw<T[W].Dist){ T[W].Dist=T[V].Dist+Cvw; T[W].Path=V; if(WisnotalreadyinQ) Enqueue(W,Q); }/*end-ifupdate*/}/*end-while*/

DisposeQueue(Q);/*freememory*/}/*negative-costcyclewillcauseindefiniteloop*//*nolongeronceperedge*//*eachvertexcandequeueatmost|V|times*/T=O(|V|

|E|)§3最短路徑算法

無環(huán)圖如果圖是無環(huán)的，頂點可以以拓撲排序的順序被選中。因為當一個頂點被選中，由于沒有來自未知頂點的入邊，它的distance不可能再降低了。T=O(|E|+|V|)，不需要優(yōu)先隊列。

應用:AOE(ActivityOnEdge)Networks——規(guī)劃一個項目vjai::=活動ai完成的標記EC[j]\LC[j]::=頂點

vj的最早\最遲完成時間

CPM(CriticalPathMethod，關鍵路徑方法)持續(xù)時間松弛時間ECTimeLCTime

頂點編號§3最短路徑算法〖例〗

一個虛擬項目的AOEnetwork012345678startfinisha0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=7a8=4a9=2a10=4

計算EC:從v0開始,對任意ai=<v,w>,我們有064577161418a11=0啞活動

計算LC:從最后一個頂點v8開始,對任意ai=<v,w>,我們有181614775660<v,w>的松弛時間

=232

關鍵路徑::=全部由零松弛邊組成的路徑。§3最短路徑算法2.所有頂點對間的最短路徑問題對所有頂點對

vi

和

vj

(i

j),找到它們之間的最短路徑。方法1使用單源最短路徑算法|V|次。T=O(|V|3)–在稀疏圖上運行較快。方法2Ch.10給出了一個O(|V|3)的算法,在稠密圖上運行較快?！?網(wǎng)絡流問題〖例〗

考慮如下管狀網(wǎng)絡：sdcbat33322214源點匯點Note:

總計進入(v)的流量

總計從(v)流出的流量

，

v{s,t}找到圖中從

s

到

t的最大流?！?網(wǎng)絡流問題1.簡單的算法sdcbat33322214GsdcbatFlowGfsdcbatResidualGrStep1:

找到圖Gr中的任意路徑s

t;增長路徑Step2:

將路徑中的最小邊作為路徑的流量，并添加路徑到

Gf

;Step3:

更新

Gr

并移去0流量的邊;Step4:If(Gr存在路徑s

t

)GotoStep1;ElseEnd.對了!如果我先選擇路徑s

a

d

t，會怎樣呢?

實際上很簡單。但是我希望你在這兒能指出一些問題。。。

呃…

看起來我們在這兒不能使用貪婪策略?！?網(wǎng)絡流問題sdcbat33322214G§4網(wǎng)絡流問題2.一個解決辦法–允許算法撤銷它的選擇對Gf中的每一條邊(v,w)，流值為fv,w

，在Gr中添加一條流值為

fv,w

的邊

。sdcbatFlowGfsdcbat33322214GsdcbatResidualGr333222143333313222222213221〖Proposition〗

如果邊的容量是有理數(shù)，這個算法將總是在最大流終止。Note:

算法對有環(huán)的圖依然有效。§4網(wǎng)絡流問題3.分析(如果容量都是整數(shù))

一條增長路徑可以用無權(quán)最短路徑算法找出。T=O()，f

是最大流。f·|E|stab10000001000000100000010000001

總是選擇那些使得流增長最大的路徑。/*修改Dijkstra算法*/T=Taugmentation*Tfindapath=O(|E|logcapmax

)*O(|E|log|V|)=O(|E|2log|V|)ifcapmaxisasmallinteger.§4網(wǎng)絡流問題

總是選擇具有最少邊數(shù)的增長路徑。T=Taugmentation*Tfindapath=O(|E|)*O(|E|·|V|)=O(|E|2|V|)/*無權(quán)最短路徑算法*/Note:

如果每個v{s,t}

擁有一條容量為1的入邊或一條容量為1的出邊，那么時間界將減少到O(|E||V|1/2).最小值流問題是要在所有最大流中找出具有最小權(quán)值的流。在這種問題中，每條邊擁有一個權(quán)值?！?最小生成樹【定義】

一棵圖G的生成樹是一棵由V(G)和E(G)的子集構(gòu)成的樹。〖例〗一個完全圖和三棵生成樹。Note:

最小生成樹

是一棵樹，因此它無環(huán)–邊數(shù)是|V|–1.它是最小的，因為邊的總權(quán)值最小。它是生成樹，因為包含了圖的所有頂點。

最小生成樹

存在，當且僅當G是連通的。向一棵生成樹添加一條非樹中的邊，將得到一個環(huán)。§5最小生成樹貪婪算法在以下約束條件下，每個階段都做出當前最好的選擇:(1)必須使用圖中的邊；(2)必須使用恰好|V|

1條邊；(3)不能使用會產(chǎn)生環(huán)的邊。1.Prim算法–growatree/*與Dijkstra算法非常相似*/v1v2v6v7v3v4v52421310758461§5最小生成樹2.Kruskal算法–maintainaforestvoidKruskal(GraphG){T={};

while(Tcontainslessthan|V|

1edges&&Eisnotempty){choosealeastcostedge(v,w)fromE;delete(v,w)fromE;

if((v,w)doesnotcreateacycleinT) add(v,w)toT;

else

discard(v,w);}

if(Tcontainsfewerthan|V|

1edges)Error(“Nospanningtree