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

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

，|V|=；集合E＝

|E|=“圖”

G可以表示為集合：G=（V,E）。每條邊是一個(gè)頂點(diǎn)對（v,w）E，并且v,wV。圖的定義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)無向圖（UndirectedGraphs）:邊（v,w）等同于邊（w,v）。用圓括號“（）”表示無向邊。(a)無向圖G1

1230G1=(V1，E1)，V1={0，1，2，3}，E1={（0,1）,（0,2）,（0,3）,（2,3）}?！?若干定義(1)無向圖（UndirectedGraphs）:邊（(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>}?！?若干定義(b)有向圖G212304(2)有向圖（Dire(3)簡單圖（SimpleGraphs）:沒有重邊和自回路的圖。1201230(a)重邊圖(b)自回路圖

本書只討論簡單圖。§1若干定義(3)簡單圖（SimpleGraphs）:沒有重邊和自回(5)路徑、簡單路徑、回路、無環(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)路徑長度::=路徑中邊的數(shù)量簡單路徑::=vi1,vi2,,vin

都是不同頂點(diǎn)回路

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

=vq

）的路徑無環(huán)圖

::=不存在任何回路的圖有向無環(huán)圖

::=不存在回路的有向圖，也稱DAG（DirectedAcyclicGraph）§1若干定義(5)路徑、簡單路徑、回路、無環(huán)圖(4)鄰接點(diǎn):如果（(7)有向完全圖：在頂點(diǎn)數(shù)給定為n的情況下，有向邊數(shù)達(dá)到最大的n(n-1)條邊。(6)無向完全圖：在頂點(diǎn)數(shù)給定為n的情況下，邊數(shù)達(dá)到最大的n(n-1)/2條邊。（因?yàn)闆]有重邊和自回路邊）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)無向圖的頂點(diǎn)連通、連通圖、連通分量：(11)圖G的子圖G’：V(G’)V(G)&&E(G’)E(G)如果無向圖從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是“連通的（Connected）”無向圖中任意兩頂點(diǎn)都是連通的，則稱該圖是“連通圖（ConnectedGraph）”。無向圖的極大連通子圖稱為“連通分量（ConnectedComponent）”。連通分量的概念包含以下4個(gè)要點(diǎn)：

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

和vj(i≠j)均既有從vi到vj的路徑，也有從vj到vi的路徑，則稱該有向圖是“強(qiáng)連通圖（StronglyConnectedGraph）”。有向圖的極大強(qiáng)連通子圖稱為“強(qiáng)連通分量（StronglyConnectedComponent）”。連通分量的概念也包含前面4個(gè)要點(diǎn)。(14)樹、生成樹：樹是圖的特例：無環(huán)的無向圖。所謂連通圖G的“生成樹（SpanningTree）”，是G的包含其全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖。它必定包含且僅包含G的n-1條邊。生成樹有可能不唯一。當(dāng)且僅當(dāng)G滿足下面4個(gè)條件之一（完全等價(jià)）：①G有n-1條邊，且沒有環(huán)；②G有n-1條邊，且是連通的；③G中的每一對頂點(diǎn)有且只有一條路徑相連；④G是連通的，但刪除任何一條邊就會使它不連通。§1若干定義(13)有向圖的強(qiáng)連通圖、連通分量：有向圖中任意一對頂點(diǎn)類型名稱：圖（Graph）操作集：對于任意的圖GGraph，頂點(diǎn)v、v1和v2

ertex，以及任一訪問頂點(diǎn)的函數(shù)visit()，操作舉例：數(shù)據(jù)對象集：一非空的頂點(diǎn)集合Vertex和一個(gè)邊集合Edge，每條邊用對應(yīng)的一對頂點(diǎn)表示。GraphCreate()：構(gòu)造并返回一個(gè)空圖；voidDestroy(GraphG)：釋放圖G占用的存儲空間；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）操作集：對于任意的圖GGra鄰接矩陣（AdjacencyMatrix）邊的信息：用鄰接矩陣A[n][n]表示為:3V0V3V2V1

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

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

無向圖的鄰接矩陣一定是一個(gè)對稱矩陣。所需存儲元素的個(gè)數(shù)是|V|×(|V|-1)/2。對于無向圖，鄰接矩陣的第i行（或第i列）非0元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度Degree(vi)。對于有向圖，鄰接矩陣的第i行（或第i列）非0元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度(vi)（或入度(vi)）。存儲空間代價(jià)為Θ(|V|2)。要確定圖中有多少條邊，所花費(fèi)的時(shí)間代價(jià)也是Θ(|V|2)。對稀疏圖來說，這樣的代價(jià)明顯是不合理的！§1.1圖的表示鄰接矩陣特點(diǎn)：無向圖的鄰接矩陣一定是一個(gè)對稱矩陣。鄰接表(AdjacencyList)對于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表，再將所有點(diǎn)的鄰接表表頭放到一個(gè)數(shù)組中，就構(gòu)成了圖的鄰接表。

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

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

指針域3V0V3V2V1§1.1圖的表示鄰接表(AdjacencyList)對于圖G中的每個(gè)頂鄰接表與逆鄰接表無向圖中有n個(gè)頂點(diǎn)和e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表邊結(jié)點(diǎn)。顯然，在邊稀疏

(e<<n(n-1)/2)的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間；無向圖的鄰接表，頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)；而在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度，為便于確定頂點(diǎn)vi的入度，可以建立一個(gè)有向圖的逆鄰接表，即對每個(gè)頂點(diǎn)vi

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

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

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

是j

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

到

j有一條路徑

i是j

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

所以

j

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

k,k

ji

j)和

非自反性(i

i

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

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

i

存在，使得

i

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

i

必須在i

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

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

i,j,如果i

是

j

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

出現(xiàn)在

j

的前面。〖例〗

一個(gè)可能的計(jì)算機(jī)科學(xué)學(xué)位課程學(xué)習(xí)表順序如下：試著用AOV圖表示出來§2拓?fù)渑判颉径x】拓?fù)渑判蚴菆D中頂點(diǎn)的一個(gè)線性排序，它求出給定DAG的一個(gè)拓?fù)湫蛄校喈?dāng)于進(jìn)行一個(gè)作業(yè)調(diào)度。如何來求一個(gè)拓?fù)湫蛄心兀亢唵嗡惴ǎ篬step1]如果找得到任何一個(gè)入度為0的頂點(diǎn)v，則step2，否則step4；[step2]輸出頂點(diǎn)v，并從圖中刪除該頂點(diǎn)以及與其相連的所有邊；[step3]對改變后的圖重復(fù)這一過程，轉(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)度。簡單算§2拓?fù)渑判騈ote:對一個(gè)圖來說，拓?fù)渑判虿皇俏ㄒ坏摹Ｈ?，要達(dá)到獲得計(jì)算機(jī)科學(xué)學(xué)位的條件有幾種途徑（拓?fù)渑判颍oal測試一個(gè)AOV的可行性，可能的話生成一個(gè)拓?fù)渑判?。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)檢查整個(gè)InDegree數(shù)組，所需時(shí)間是O(|V|)，此函數(shù)被調(diào)用|V|次，故本算法的時(shí)間復(fù)雜性為

O(|V|2)§2拓?fù)渑判騈ote:對一個(gè)圖來說，拓?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è)【例】交通的最短路徑選擇。最短路徑有不同含義。【例】交通的最短路徑選擇。最短路徑有不同含義。§3最短路徑算法給定一個(gè)圖G=(V,E),以及權(quán)值方程

c(e)，e

E(G)。

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

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

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

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

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

無權(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最短路徑算法無權(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*/}v1v2v6v7v3v4v50v1Dist

Pathv20v3v4v5v6v70000000v3v71v3v11v3v61122v1v222v1v433v2v533v4T=O(|V|+|E|)§3最短路徑算法改進(jìn)算法voidUnweighte

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

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

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

S={s

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

vi}對任意

u

S,定義

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

(vi

S)u}。如果路徑都是按非降序生成的，那么最短路徑必然只經(jīng)過

vi

S;當(dāng)distance[u]=min{wS|distance[w]}，

(如果

u

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

被選中如果

distance[u1]<distance[u2]

，并且

u1

被加入

S,那么

distance[u2]

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

s

到

u2

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

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(;;)*/}v1v2v6v7v3v4v524213102584610v1DistPathv2v3v4v5v6v700000002v11v13v43v49v45v48v36v7/*notworkforedgewithnegativecost*/圖9.31實(shí)現(xiàn)了打印路徑的例程。/*O(|V|)*/§3最短路徑算法voidDijkstra(Table§3最短路徑算法

實(shí)現(xiàn)1V=最小的未知距離頂點(diǎ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):配對堆(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最短路徑算法

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

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

vj的最早\最遲完成時(shí)間CPM(CriticalPathMethod，關(guān)鍵路徑方法)持續(xù)時(shí)間松弛時(shí)間ECTimeLCTime

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

一個(gè)虛擬項(xiàng)目的AOEnetwork012345678startfinisha0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=7a8=4a9=2a10=4計(jì)算EC:從v0開始,對任意ai=<v,w>,我們有064577161418a11=0啞活動計(jì)算LC:從最后一個(gè)頂點(diǎn)v8開始,對任意ai=<v,w>,我們有181614775660<v,w>的松弛時(shí)間

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

vi

和

vj

(i

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

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

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

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

，

v{s,t}找到圖中從

s

到

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

找到圖Gr中的任意路徑s

t;增長路徑Step2:

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

Gf

;Step3:

更新

Gr

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

t

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

adt，會怎樣呢?

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

呃…

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

，在Gr中添加一條流值為

fv,w

的邊

。sdcbatFlowGfsdcbat33322214GsdcbatResidualGr333222143333313222222213221〖Proposition〗

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

算法對有環(huán)的圖依然有效?！?網(wǎng)絡(luò)流問題2.一個(gè)解決辦法–允許算法撤銷它的選§4網(wǎng)絡(luò)流問題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)絡(luò)流問題3.分析(如果容量都是整數(shù))一§4網(wǎng)絡(luò)流問題總是選擇具有最少邊數(shù)的增長路徑。T=Taugmentation*Tfindapath=O(|E|)*O(|E|·|V|)=O(|E|2|V|)/*無權(quán)最短路徑算法*/Note:

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

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

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

最小生成樹

是一棵樹，因此它無環(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)不能使用會產(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最小生成樹2.Kruskal算法–maint§7NP-完全性介紹

回顧:

單源無權(quán)最短路徑問題

單源無權(quán)最長路徑問題

沒有

已知算法能在多項(xiàng)式時(shí)間內(nèi)解決§7NP-完全性介紹回顧:單源無權(quán)最短路徑問題§7NP-完全性【例】停機(jī)問題:是否能讓C編譯器檢查所有的無限循環(huán)？回答:No.證明:

如果存在一個(gè)無限循環(huán)檢測的程序，那么它肯定可以用于自檢。Loop(P){/*1*/

if(P(P)loops) print(YES);/*2*/elseinfinite_loop();}如果是Loop(Loop)將發(fā)生什么

?

中止

/*2*/istrueLoops

無限循環(huán)

/*1*/istrue中止

難與易

最容易:O(N)–因?yàn)槲覀冎辽僖x入輸入數(shù)據(jù)。最困難:–不可判定問題§7NP-完全性【例】停機(jī)問題:是否能讓C編譯器檢查不可判定問題仍然是不可判定的?！?NP-完全性確定型圖靈機(jī)在每一時(shí)刻都在執(zhí)行一條指令。根據(jù)這條指令，機(jī)器再去執(zhí)行某條接下來的指令，這是唯一確定的。非確定型圖靈機(jī)i對其后的步驟是有選擇的，它可以自由進(jìn)行任意的選擇。如果這些步驟中有一條導(dǎo)致問題的解，那么它將總是選擇這個(gè)正確的步驟。NP:非確定型多項(xiàng)式時(shí)間（Nondeterministicpolynomial-time）如果我們在多項(xiàng)式時(shí)間內(nèi)能證明一個(gè)問題的任意“是”的實(shí)例是正確的，問題就屬于NP類。【例】Hamilton回路問題:

找到一個(gè)包含所有頂點(diǎn)的簡單回路–這個(gè)簡單回路是否包含所有頂點(diǎn)？NPNote:

并非所有可判定問題都屬于NP.例如，考慮確定一個(gè)圖是否沒有Hamiltonian回路的問題。

NP類不可判定問題仍然是不可判定的?！?NP-完全性確定型圖靈§7NP-完全性

NP完全問題--最難的問題NP完全問題

有一個(gè)性質(zhì)，即NP中的任一問題都能夠多項(xiàng)式地歸約成NP完全問題。如果我們能以多項(xiàng)式時(shí)間解決任意的NP完全問題，那么我們就能夠以多項(xiàng)式時(shí)間解決所有的NP問題！【例】假設(shè)我們已知Hamilton回路問題是NP完全問題，證明旅行商問題也是NP完全問題。旅行商問題（TSP）:給定一個(gè)完全圖G=(V,E)、其邊的權(quán)值及整數(shù)K，是否存在一個(gè)訪問所有頂點(diǎn)并且總值K的簡單回路?§7NP-完全性NP完全問題--最難的問題NP完全證明:

TSP顯然是NP的，因?yàn)槠浣夂苋菀昨?yàn)證?！?NP-完全性V1V2V3V4V51111112222K=|V|G有一個(gè)Hamilton回路，當(dāng)且僅當(dāng)

G’

有一個(gè)總權(quán)值為|V|的旅行商回路。第一個(gè)被證明為NP完全的問題是可滿足性問題：輸入一個(gè)布爾表達(dá)式，并提問是否該表達(dá)式對式中各變量的一次賦值取值為ture。Cook于1971年通過直接證明NP中所有問題都可以變換成可滿足性問題，而證明了可滿足性問題是NP完全的。他使用一臺圖靈非確定型機(jī)器在多項(xiàng)式時(shí)間求解了此問題。證明:TSP顯然是NP的，因?yàn)槠浣夂苋菀昨?yàn)證。§7AboutExamination題型及分?jǐn)?shù)分布單項(xiàng)選擇題（約20’）填空題（約15’）算法設(shè)計(jì)與實(shí)現(xiàn)（約5-10’）應(yīng)用題復(fù)習(xí)著重在習(xí)題和例題AboutExamination題型及分?jǐn)?shù)分布人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋。”通過閱讀科技書籍，我們能豐富知識，培養(yǎng)邏輯思維能力；通過閱讀文學(xué)作品，我們能提高文學(xué)鑒賞水平，培養(yǎng)文學(xué)情趣；通過閱讀報(bào)刊，我們能增長見識，擴(kuò)大自己的知識面。有許多書籍還能培養(yǎng)我們的道德情操，給我們巨大的精神力量，鼓舞我們前進(jìn)。人有了知識，就會具備各種分析能力，湘潭大學(xué)數(shù)據(jù)結(jié)構(gòu)課件Ch09Graph講義第9章圖論算法第9章圖論算法介紹幾個(gè)現(xiàn)實(shí)生活中發(fā)生的問題，可以轉(zhuǎn)化成圖論算法；解決幾個(gè)普通的圖論問題的算法；深度優(yōu)先搜索(depth-firstsearch)技巧；……介紹幾個(gè)現(xiàn)實(shí)生活中發(fā)生的問題，可以轉(zhuǎn)化成圖論算法；【例】圖中村與村之間的道路是一個(gè)較長遠(yuǎn)的規(guī)劃目標(biāo)?！?引子最小生成樹問題9.5節(jié)討論[問題1]公路村村通項(xiàng)目要求用最小的投入實(shí)現(xiàn)每個(gè)村都能夠有公路通達(dá)。那么應(yīng)該選擇建設(shè)哪些道路可以使這個(gè)投資最小呢？（假設(shè)每條道路的建設(shè)成本已知）【例】圖中村與村之間的道路是一個(gè)較長遠(yuǎn)的規(guī)劃目標(biāo)?！?引【例】下圖為公路規(guī)劃抽象及造價(jià)預(yù)算示例圖?！?引子[問題2]在同樣的抽象圖中，假設(shè)把“造價(jià)”的含義修改成“距離”，那么我們就可以問：要走遍每個(gè)村莊，并回到起點(diǎn)，該如何走才能夠使得總的路程最短？88756655444532745BCDFLHWXYZ巡回售貨員問題（TSP）P.253討論【例】下圖為公路規(guī)劃抽象及造價(jià)預(yù)算示例圖。§0引子[問題通常：用|V|表示頂點(diǎn)的數(shù)量（|V|≥1），用|E|表示邊的數(shù)量（|E|≥0）。[例]上圖給出了一個(gè)圖的示例，在該圖中：集合V＝

，|V|=；集合E＝

|E|=“圖”

G可以表示為集合：G=（V,E）。每條邊是一個(gè)頂點(diǎn)對（v,w）E，并且v,wV。圖的定義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)無向圖（UndirectedGraphs）:邊（v,w）等同于邊（w,v）。用圓括號“（）”表示無向邊。(a)無向圖G1

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

12304(2)有向圖（DirectedGraphs）:邊<v,w>不同于邊<w,v>。用尖括號“<>”表示有向邊；有向邊也稱“?。ˋ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>}。§1若干定義(b)有向圖G212304(2)有向圖（Dire(3)簡單圖（SimpleGraphs）:沒有重邊和自回路的圖。1201230(a)重邊圖(b)自回路圖

本書只討論簡單圖。§1若干定義(3)簡單圖（SimpleGraphs）:沒有重邊和自回(5)路徑、簡單路徑、回路、無環(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)路徑長度::=路徑中邊的數(shù)量簡單路徑::=vi1,vi2,,vin

都是不同頂點(diǎn)回路

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

=vq

）的路徑無環(huán)圖

::=不存在任何回路的圖有向無環(huán)圖

::=不存在回路的有向圖，也稱DAG（DirectedAcyclicGraph）§1若干定義(5)路徑、簡單路徑、回路、無環(huán)圖(4)鄰接點(diǎn):如果（(7)有向完全圖：在頂點(diǎn)數(shù)給定為n的情況下，有向邊數(shù)達(dá)到最大的n(n-1)條邊。(6)無向完全圖：在頂點(diǎn)數(shù)給定為n的情況下，邊數(shù)達(dá)到最大的n(n-1)/2條邊。（因?yàn)闆]有重邊和自回路邊）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)無向圖的頂點(diǎn)連通、連通圖、連通分量：(11)圖G的子圖G’：V(G’)V(G)&&E(G’)E(G)如果無向圖從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是“連通的（Connected）”無向圖中任意兩頂點(diǎn)都是連通的，則稱該圖是“連通圖（ConnectedGraph）”。無向圖的極大連通子圖稱為“連通分量（ConnectedComponent）”。連通分量的概念包含以下4個(gè)要點(diǎn)：

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

和vj(i≠j)均既有從vi到vj的路徑，也有從vj到vi的路徑，則稱該有向圖是“強(qiáng)連通圖（StronglyConnectedGraph）”。有向圖的極大強(qiáng)連通子圖稱為“強(qiáng)連通分量（StronglyConnectedComponent）”。連通分量的概念也包含前面4個(gè)要點(diǎn)。(14)樹、生成樹：樹是圖的特例：無環(huán)的無向圖。所謂連通圖G的“生成樹（SpanningTree）”，是G的包含其全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖。它必定包含且僅包含G的n-1條邊。生成樹有可能不唯一。當(dāng)且僅當(dāng)G滿足下面4個(gè)條件之一（完全等價(jià)）：①G有n-1條邊，且沒有環(huán)；②G有n-1條邊，且是連通的；③G中的每一對頂點(diǎn)有且只有一條路徑相連；④G是連通的，但刪除任何一條邊就會使它不連通。§1若干定義(13)有向圖的強(qiáng)連通圖、連通分量：有向圖中任意一對頂點(diǎn)類型名稱：圖（Graph）操作集：對于任意的圖GGraph，頂點(diǎn)v、v1和v2

ertex，以及任一訪問頂點(diǎn)的函數(shù)visit()，操作舉例：數(shù)據(jù)對象集：一非空的頂點(diǎn)集合Vertex和一個(gè)邊集合Edge，每條邊用對應(yīng)的一對頂點(diǎn)表示。GraphCreate()：構(gòu)造并返回一個(gè)空圖；voidDestroy(GraphG)：釋放圖G占用的存儲空間；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）操作集：對于任意的圖GGra鄰接矩陣（AdjacencyMatrix）邊的信息：用鄰接矩陣A[n][n]表示為:3V0V3V2V1

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

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

無向圖的鄰接矩陣一定是一個(gè)對稱矩陣。所需存儲元素的個(gè)數(shù)是|V|×(|V|-1)/2。對于無向圖，鄰接矩陣的第i行（或第i列）非0元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度Degree(vi)。對于有向圖，鄰接矩陣的第i行（或第i列）非0元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度(vi)（或入度(vi)）。存儲空間代價(jià)為Θ(|V|2)。要確定圖中有多少條邊，所花費(fèi)的時(shí)間代價(jià)也是Θ(|V|2)。對稀疏圖來說，這樣的代價(jià)明顯是不合理的！§1.1圖的表示鄰接矩陣特點(diǎn)：無向圖的鄰接矩陣一定是一個(gè)對稱矩陣。鄰接表(AdjacencyList)對于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表，再將所有點(diǎn)的鄰接表表頭放到一個(gè)數(shù)組中，就構(gòu)成了圖的鄰接表。

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

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

指針域3V0V3V2V1§1.1圖的表示鄰接表(AdjacencyList)對于圖G中的每個(gè)頂鄰接表與逆鄰接表無向圖中有n個(gè)頂點(diǎn)和e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表邊結(jié)點(diǎn)。顯然，在邊稀疏

(e<<n(n-1)/2)的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間；無向圖的鄰接表，頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)；而在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度，為便于確定頂點(diǎn)vi的入度，可以建立一個(gè)有向圖的逆鄰接表，即對每個(gè)頂點(diǎn)vi

建立一個(gè)鏈接以vi為頭的弧的鏈表。例如：§1.1圖的表示鄰接表與逆鄰接表無向圖中有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)表示活動（如：課程），E(G)表示優(yōu)先關(guān)系(如

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

是j

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

到

j有一條路徑

i是j

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

所以

j

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

k,k

ji

j)和

非自反性(i

i

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

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

i

存在，使得

i

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

i

必須在i

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

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

i,j,如果i

是

j

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

出現(xiàn)在

j

的前面。〖例〗

一個(gè)可能的計(jì)算機(jī)科學(xué)學(xué)位課程學(xué)習(xí)表順序如下：試著用AOV圖表示出來§2拓?fù)渑判颉径x】拓?fù)渑判蚴菆D中頂點(diǎn)的一個(gè)線性排序，它求出給定DAG的一個(gè)拓?fù)湫蛄?，相?dāng)于進(jìn)行一個(gè)作業(yè)調(diào)度。如何來求一個(gè)拓?fù)湫蛄心?？簡單算法：[step1]如果找得到任何一個(gè)入度為0的頂點(diǎn)v，則step2，否則step4；[step2]輸出頂點(diǎn)v，并從圖中刪除該頂點(diǎn)以及與其相連的所有邊；[step3]對改變后的圖重復(fù)這一過程，轉(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)度。簡單算§2拓?fù)渑判騈ote:對一個(gè)圖來說，拓?fù)渑判虿皇俏ㄒ坏?。如，要達(dá)到獲得計(jì)算機(jī)科學(xué)學(xué)位的條件有幾種途徑（拓?fù)渑判颍?。Goal測試一個(gè)AOV的可行性，可能的話生成一個(gè)拓?fù)渑判?。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)檢查整個(gè)InDegree數(shù)組，所需時(shí)間是O(|V|)，此函數(shù)被調(diào)用|V|次，故本算法的時(shí)間復(fù)雜性為

O(|V|2)§2拓?fù)渑判騈ote:對一個(gè)圖來說，拓?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|)MistakesinFig