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

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

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

，|V|=；集合E＝

|E|=“圖”

G可以表示為集合：G=（V,E）。每條邊是一個(gè)頂點(diǎn)對(duì)（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。通常：用|V|表示頂點(diǎn)的數(shù)量（|V|≥1），[例(1)無(wú)向圖（UndirectedGraphs）:邊（v,w）等同于邊（w,v）。用圓括號(hào)“（）”表示無(wú)向邊。(a)無(wú)向圖G1

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

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

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

圖G中從vp

到vq

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

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

簡(jiǎn)單路徑::=vi1,vi2,,vin

都是不同頂點(diǎn)

回路

::=起點(diǎn)和終點(diǎn)相同（vp

=vq

）的路徑

無(wú)環(huán)圖

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

有向無(wú)環(huán)圖

::=不存在回路的有向圖，也稱DAG（DirectedAcyclicGraph）§1若干定義(5)路徑、簡(jiǎn)單路徑、回路、無(wú)環(huán)圖(4)鄰接點(diǎn):如果（(7)有向完全圖：在頂點(diǎn)數(shù)給定為n的情況下，有向邊數(shù)達(dá)到最大的n(n-1)條邊。(6)無(wú)向完全圖：在頂點(diǎn)數(shù)給定為n的情況下，邊數(shù)達(dá)到最大的n(n-1)/2條邊。（因?yàn)闆](méi)有重邊和自回路邊）02130213(8)頂點(diǎn)的度(degree)、入度(in-degree)、出度(out-degree)：

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

給定

n

個(gè)頂點(diǎn)和e

條邊的圖G,

則有:§1若干定義(7)有向完全圖：在頂點(diǎn)數(shù)給定為n的情況下，有向邊數(shù)達(dá)到最大(10)權(quán)（Cost）、網(wǎng)絡(luò)（Network）(9)稠密圖、稀疏圖：是否滿足|E|>|V|log2|V|，作為稠密圖和稀疏圖的分界條件。(12)無(wú)向圖的頂點(diǎn)連通、連通圖、連通分量：(11)圖G的子圖G’：V(G’)V(G)&&E(G’)E(G)

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

無(wú)向圖中任意兩頂點(diǎn)都是連通的，則稱該圖是“連通圖（ConnectedGraph）”。

無(wú)向圖的極大連通子圖稱為“連通分量（ConnectedComponent）”。連通分量的概念包含以下4個(gè)要點(diǎn)：

子圖、連通、極大頂點(diǎn)數(shù)、極大邊數(shù)§1若干定義(10)權(quán)（Cost）、網(wǎng)絡(luò)（Network）(9)稠(13)有向圖的強(qiáng)連通圖、連通分量：

有向圖中任意一對(duì)頂點(diǎn)vi

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

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

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

Graph，頂點(diǎn)v、v1和v2

ertex，以及任一訪問(wèn)頂點(diǎn)的函數(shù)visit()，操作舉例：數(shù)據(jù)對(duì)象集：一非空的頂點(diǎn)集合Vertex和一個(gè)邊集合Edge，每條邊用對(duì)應(yīng)的一對(duì)頂點(diǎn)表示。

GraphCreate()：構(gòu)造并返回一個(gè)空?qǐng)D；

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

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

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

GraphDFS（GraphG,Vertexv,visit()）：在圖G中，從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷；……§1若干定義類型名稱：圖（Graph）操作集：對(duì)于任意的圖GGra鄰接矩陣（AdjacencyMatrix）

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

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

圖的表示

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

特點(diǎn)：

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

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

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

存儲(chǔ)空間代價(jià)為Θ(|V|2)。要確定圖中有多少條邊，所花費(fèi)的時(shí)間代價(jià)也是Θ(|V|2)。對(duì)稀疏圖來(lái)說(shuō)，這樣的代價(jià)明顯是不合理的！§1.1圖的表示鄰接矩陣特點(diǎn)：無(wú)向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。鄰接表(AdjacencyList)

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

無(wú)向圖的鄰接表表示示例VertexFirstEdge頂點(diǎn)域

邊表頭指針AdjVNext鄰接點(diǎn)域

指針域3V0V3V2V1§1.1圖的表示鄰接表(AdjacencyList)對(duì)于圖G中的每個(gè)頂鄰接表與逆鄰接表

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

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

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

建立一個(gè)鏈接以vi為頭的弧的鏈表。例如：§1.1圖的表示鄰接表與逆鄰接表無(wú)向圖中有n個(gè)頂點(diǎn)和e條邊，則它的鄰接表§2拓?fù)渑判颉祭?/p>

獲得一個(gè)計(jì)算機(jī)科學(xué)學(xué)位所需的課程。怎么把這個(gè)表轉(zhuǎn)換成圖表示?§2拓?fù)渑判颉祭将@得一個(gè)計(jì)算機(jī)科學(xué)學(xué)位所需的課程?！?拓?fù)渑判駻OV網(wǎng)::=圖G中V(G)表示活動(dòng)（如：課程），E(G)表示優(yōu)先關(guān)系(如

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

i

是j

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

到

j有一條路徑

i是j

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

所以

j

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

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

k,k

j

i

j)和

非自反性(i

i

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

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

i

存在，使得

i

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

i

必須在i

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

它必然是非自反的?！?拓?fù)渑判駻OV網(wǎng)::=圖G中V(§2拓?fù)渑判颉径x】拓?fù)渑判蚴菆D中頂點(diǎn)的一個(gè)線性排序，它使得對(duì)任意兩個(gè)頂點(diǎn)

i,j,如果i

是

j

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

出現(xiàn)在

j

的前面。〖例〗

一個(gè)可能的計(jì)算機(jī)科學(xué)學(xué)位課程學(xué)習(xí)表順序如下：試著用AOV圖表示出來(lái)§2拓?fù)渑判颉径x】拓?fù)渑判蚴菆D中頂點(diǎn)的一個(gè)線性排序，它求出給定DAG的一個(gè)拓?fù)湫蛄校喈?dāng)于進(jìn)行一個(gè)作業(yè)調(diào)度。如何來(lái)求一個(gè)拓?fù)湫蛄心兀亢?jiǎn)單算法：[step1]如果找得到任何一個(gè)入度為0的頂點(diǎn)v，則step2，否則step4；[step2]輸出頂點(diǎn)v，并從圖中刪除該頂點(diǎn)以及與其相連的所有邊；[step3]對(duì)改變后的圖重復(fù)這一過(guò)程，轉(zhuǎn)step1；[step4]如果已經(jīng)輸出全部頂點(diǎn)，則結(jié)束；否則該有向圖不是DAG。

理論依據(jù)是基于下面的結(jié)論：一個(gè)頂點(diǎn)數(shù)|V|>1的有向圖，如果每個(gè)頂點(diǎn)的入度都大于0，那么它必定存在回路。求出給定DAG的一個(gè)拓?fù)湫蛄?，相?dāng)于進(jìn)行一個(gè)作業(yè)調(diào)度。簡(jiǎn)單算§2拓?fù)渑判騈ote:對(duì)一個(gè)圖來(lái)說(shuō)，拓?fù)渑判虿皇俏ㄒ坏?。如，要達(dá)到獲得計(jì)算機(jī)科學(xué)學(xué)位的條件有幾種途徑（拓?fù)渑判颍?。Goal測(cè)試一個(gè)AOV的可行性，可能的話生成一個(gè)拓?fù)渑判颉oidTopsort(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)檢查整個(gè)InDegree數(shù)組，所需時(shí)間是O(|V|)，此函數(shù)被調(diào)用|V|次，故本算法的時(shí)間復(fù)雜性為

O(|V|2)§2拓?fù)渑判騈ote:對(duì)一個(gè)圖來(lái)說(shuō)，拓?fù)渑判虿皇俏ㄒ弧?拓?fù)渑判?/p>

實(shí)現(xiàn):

將所有度為0的未標(biāo)記頂點(diǎn)放在一個(gè)特殊的盒子里（隊(duì)列或棧）。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§2拓?fù)渑判驅(qū)崿F(xiàn):將所有度為0的未標(biāo)記頂點(diǎn)放在一個(gè)【例】交通的最短路徑選擇。最短路徑有不同含義?！纠拷煌ǖ淖疃搪窂竭x擇。最短路徑有不同含義?！?最短路徑算法給定一個(gè)圖G=(V,E),以及權(quán)值方程

c(e)，e

E(G)。

從源點(diǎn)到目標(biāo)點(diǎn)的路徑P

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

G=(V,E),以及一個(gè)指定頂點(diǎn)s,找到從s

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

的最短路徑定義為0。§3最短路徑算法給定一個(gè)圖G=(V,E),以§3最短路徑算法

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

v31:

v1andv6112:

v2andv4223:

v5andv733

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

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

/*initializedtobeexceptfors*/Table[i].Known::=1ifviischecked;or0ifnotTable[i].Path::=fortrackingthepath/*initializedtobe0*/§3最短路徑算法無(wú)權(quán)最短路徑v1v2v6v7v3v§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

未標(biāo)記，但Dist<Infinity,那么

Dist

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

改進(jìn)算法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|)§3最短路徑算法改進(jìn)算法voidUnweighte

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

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

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

S={s

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

vi}對(duì)任意

u

S,定義

distance[u]=最小長(zhǎng)度路徑{s

(vi

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

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

vi

S;

當(dāng)distance[u]=min{w

S|distance[w]}，

(如果

u

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

被選中

如果

distance[u1]<distance[u2]

，并且

u1

被加入

S,那么

distance[u2]

可能會(huì)變化。如果是這樣，從

s

到

u2

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

u1

，且

distance’[u2]=distance[u1]+length(<u1,u2>).為什么?如果不是這樣，那么§3最短路徑算法§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實(shí)現(xiàn)了打印路徑的例程。/*O(|V|)*/§3最短路徑算法voidDijkstra(Table§3最短路徑算法

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

實(shí)現(xiàn)2V=最小的未知距離頂點(diǎn);/*將distances放在優(yōu)先隊(duì)列里，并調(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)先隊(duì)列*//*必須連續(xù)執(zhí)行DeleteMin知道一個(gè)未知頂點(diǎn)出現(xiàn)*/如果圖是稀疏的，這種方法較好T=O(|E|log|V|)但要求|E|次DeleteMin及|E|的空間。

其他改進(jìn):配對(duì)堆(Ch.12)與Fibonacci堆(Ch.11)§3最短路徑算法實(shí)現(xiàn)1V=最小的未知距離頂點(diǎn)；§3最短路徑算法

具有負(fù)值邊的圖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最短路徑算法具有負(fù)值邊的圖HeyIhave§3最短路徑算法

無(wú)環(huán)圖如果圖是無(wú)環(huán)的，頂點(diǎn)可以以拓?fù)渑判虻捻樞虮贿x中。因?yàn)楫?dāng)一個(gè)頂點(diǎn)被選中，由于沒(méi)有來(lái)自未知頂點(diǎn)的入邊，它的distance不可能再降低了。T=O(|E|+|V|)，不需要優(yōu)先隊(duì)列。

應(yīng)用:AOE(ActivityOnEdge)Networks——規(guī)劃一個(gè)項(xiàng)目vjai::=活動(dòng)ai完成的標(biāo)記EC[j]\LC[j]::=頂點(diǎn)

vj的最早\最遲完成時(shí)間

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

頂點(diǎn)編號(hào)§3最短路徑算法無(wú)環(huán)圖如果圖是無(wú)環(huán)的，頂點(diǎn)可以以拓§3最短路徑算法〖例〗

一個(gè)虛擬項(xiàng)目的AOEnetwork012345678startfinisha0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=7a8=4a9=2a10=4

計(jì)算EC:從v0開始,對(duì)任意ai=<v,w>,我們有064577161418a11=0啞活動(dòng)

計(jì)算LC:從最后一個(gè)頂點(diǎn)v8開始,對(duì)任意ai=<v,w>,我們有181614775660<v,w>的松弛時(shí)間

=232

關(guān)鍵路徑::=全部由零松弛邊組成的路徑?！?最短路徑算法〖例〗一個(gè)虛擬項(xiàng)目的AOEnetw§3最短路徑算法2.所有頂點(diǎn)對(duì)間的最短路徑問(wèn)題對(duì)所有頂點(diǎn)對(duì)

vi

和

vj

(i

j),找到它們之間的最短路徑。方法1使用單源最短路徑算法|V|次。T=O(|V|3)–在稀疏圖上運(yùn)行較快。方法2Ch.10給出了一個(gè)O(|V|3)的算法,在稠密圖上運(yùn)行較快?！?最短路徑算法2.所有頂點(diǎn)對(duì)間的最短路徑問(wèn)題對(duì)所有§4網(wǎng)絡(luò)流問(wèn)題〖例〗

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

總計(jì)進(jìn)入(v)的流量

總計(jì)從(v)流出的流量

，

v{s,t}找到圖中從

s

到

t的最大流?！?網(wǎng)絡(luò)流問(wèn)題〖例〗考慮如下管狀網(wǎng)絡(luò)：sdcbat3§4網(wǎng)絡(luò)流問(wèn)題1.簡(jiǎn)單的算法sdcbat33322214GsdcbatFlowGfsdcbatResidualGrStep1:

找到圖Gr中的任意路徑s

t;增長(zhǎng)路徑Step2:

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

Gf

;Step3:

更新

Gr

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

t

)GotoStep1;ElseEnd.§4網(wǎng)絡(luò)流問(wèn)題1.簡(jiǎn)單的算法sdcbat333222對(duì)了!如果我先選擇路徑s

a

d

t，會(huì)怎樣呢?

實(shí)際上很簡(jiǎn)單。但是我希望你在這兒能指出一些問(wèn)題。。。

呃…

看起來(lái)我們?cè)谶@兒不能使用貪婪策略?！?網(wǎng)絡(luò)流問(wèn)題sdcbat33322214G對(duì)了!實(shí)際上很簡(jiǎn)單。但是§4網(wǎng)絡(luò)流問(wèn)題2.一個(gè)解決辦法–允許算法撤銷它的選擇對(duì)Gf中的每一條邊(v,w)，流值為fv,w

，在Gr中添加一條流值為

fv,w

的邊

。sdcbatFlowGfsdcbat33322214GsdcbatResidualGr333222143333313222222213221〖Proposition〗

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

算法對(duì)有環(huán)的圖依然有效?！?網(wǎng)絡(luò)流問(wèn)題2.一個(gè)解決辦法–允許算法撤銷它的選§4網(wǎng)絡(luò)流問(wèn)題3.分析(如果容量都是整數(shù))

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

是最大流。f·|E|stab10000001000000100000010000001

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

)*O(|E|log|V|)=O(|E|2log|V|)ifcapmaxisasmallinteger.§4網(wǎng)絡(luò)流問(wèn)題3.分析(如果容量都是整數(shù))一§4網(wǎng)絡(luò)流問(wèn)題

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

如果每個(gè)v{s,t}

擁有一條容量為1的入邊或一條容量為1的出邊，那么時(shí)間界將減少到O(|E||V|1/2).最小值流問(wèn)題是要在所有最大流中找出具有最小權(quán)值的流。在這種問(wèn)題中，每條邊擁有一個(gè)權(quán)值?！?網(wǎng)絡(luò)流問(wèn)題總是選擇具有最少邊數(shù)的增長(zhǎng)路徑。T=§5最小生成樹【定義】

一棵圖G的生成樹是一棵由V(G)和E(G)的子集構(gòu)成的樹?！祭揭粋€(gè)完全圖和三棵生成樹。Note:

最小生成樹

是一棵樹，因此它無(wú)環(huán)–邊數(shù)是|V|–1.它是最小的，因?yàn)檫叺目倷?quán)值最小。它是生成樹，因?yàn)榘藞D的所有頂點(diǎn)。

最小生成樹

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

1條邊；(3)不能使用會(huì)產(chǎn)生環(huán)的邊。1.Prim算法–growatree/*與Dijkstra算法非常相似*/v1v2v6v7v3v4v52421310758461§5最小生成樹貪婪算法在以下約束條件下，每個(gè)階段都做出當(dāng)§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”);}/*DeleteMin*//*Union/Find*/更詳細(xì)的偽代碼在圖9.58中給出T=O(|E|log|E|)§5最小生成樹