數(shù)據(jù)結(jié)構(gòu)與算法：第4章 圖以及與圖有關(guān)的算法

4.1基本術(shù)語(yǔ)4.2圖的表示

4.3圖的搜索算法4.4圖與樹的聯(lián)系

4.5無(wú)向圖的雙連通性*4.6有向圖的搜索

4.7強(qiáng)連通圖

4.8拓?fù)浞诸?4.9關(guān)鍵路徑

4.10單源最短路徑*4.11每一對(duì)頂點(diǎn)間的最短路徑第4章圖以及與圖有關(guān)的算法4.1基本定義/術(shù)語(yǔ)[定義]一個(gè)圖G=（V，E）是一個(gè)由非空的有限集V和一個(gè)邊集E所組成的。若E中的每條邊都是頂點(diǎn)的有序?qū)Γ╲,w），就說該圖是有向圖（directedgraph，digraph）。若E中的每條邊是兩個(gè)不同頂點(diǎn)無(wú)序?qū)Γ驼f該圖是無(wú)向圖，其邊仍表示成（v,w）。[ADT]GraphG=(V,R)

數(shù)據(jù)對(duì)象v：v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：

R={VR}VR={<v,w>|v,w∈V,且P(v,w),<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}操作：NodeNewNode(G,v)VoidDelNode(G,v)VoidSetSucc(G,v1,v2)VoidDelSucc(G,v1,v2)ListofnodeSucc(G,v)LisyofnodePred(G,v)IntIsEdge(G,v1,v2)NodeFirstAdjVex(G,v)NodeNextAdjVex(G,v,w)術(shù)語(yǔ)：頂點(diǎn)弧/邊鄰接/相鄰依附路徑（路）簡(jiǎn)單路徑環(huán)路帶標(biāo)號(hào)的圖（網(wǎng)）

連通連通圖

強(qiáng)連通圖連通分量完全圖稀疏圖稠密圖子圖度入度出度生成樹V3V1V4V5V2G2V1V3V4V2G10110000000011000G1.arcs0101010101010111010001100G2.arcs126543545983516∞3∞∞∞1∞∞5∞3∞∞∞∞4∞∞98∞∞∞∞6∞∞5∞∞∞∞∞∞∞534.2圖的表示1、圖的順序存儲(chǔ)——鄰接矩陣設(shè)圖G=(V,E)，V={0，1，…，n-1}則表示G的鄰接矩陣A是其元素按下式定義的n*n矩陣:A[i][j]=1若（i,j）∈E0若（i,j）∈E網(wǎng)的鄰接矩陣可定義為：A[i][j]=wij

若（i,j）∈E∞

若（i,j）∈ETD(vi)=∑A[i][j]=∑A[j][i](n頂點(diǎn)個(gè)數(shù)）j=0n-1j=0n-1TD(vi)=OD(vi)+ID(vi)=∑A[i][j]＋∑A[j][i](n頂點(diǎn)個(gè)數(shù)）j=0n-1j=0n-1#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20Typedefenum{DG,DN,AG,AN}GraphKind;TypedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{VertexTypevex[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;

GraphKindkind;}Mgraph;例：圖類型變量：MgraphG;頂點(diǎn)個(gè)數(shù)：G.vexnum弧/邊的個(gè)數(shù)：G.arcnum圖的類型：G.kind=(DG,DN,AG,AN)頂點(diǎn)i信息：G.vex[i]頂點(diǎn)i和頂點(diǎn)j鄰接關(guān)系：G.arcs[i][j].adj弧/邊附加信息：G.arcs[i][j].info->v1

v2

v3

v4

2130^^^有向圖G2鄰接表0123v1

v2

v3

v4

3002^^^^G2的逆鄰接表0123無(wú)向圖G1鄰接表v5

v1

v2

v3

v4

314243202101^^^^^01234V3V1V4V5V2G1V1V3V4V2G2＋2、圖的鏈?zhǔn)酱鎯?chǔ)——鄰接表（AdjacencyList）2、圖的鏈?zhǔn)酱鎯?chǔ)——鄰接表（AdjacencyList）Adjvexnextarcinfo表結(jié)點(diǎn)datafirstarc頭結(jié)點(diǎn)#defineMAX_VERTEX_NUM20TypedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;TypedefstructVnode{VertexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];Typedefstruct{AdjListvertices;Intvexnum;Intkind;}ALGraph;例：圖類型變量：ALgraphG;頂點(diǎn)個(gè)數(shù)：G.vexnum圖的類型：G.kind=(DG,DN,AG,AN)頂點(diǎn)i信息：G.vertices[i].dada頂點(diǎn)i的第一個(gè)鄰接點(diǎn):G.vertices[i].firstarc->adjvexG.vertices[G.vertices[i].firstarc->adjvex].dataG.vertices[i].firstarc->info頂點(diǎn)i的第二個(gè)鄰接點(diǎn)：G.vertices[i].firstarc->nextarc->adjvex4.3圖的搜索算法深度優(yōu)先搜索DFS(Depth-Firstsearch)廣度優(yōu)先搜索BFS(Breadth-Firstsearch)圖的遍歷確定遍歷起點(diǎn)為保證非連通圖的每一頂點(diǎn)都能被訪問到，應(yīng)輪換起點(diǎn)為避免頂點(diǎn)的重復(fù)訪問，做訪問標(biāo)記遍歷圖注意問題：1、深度優(yōu)先搜索DFS(Depth-Firstsearch)

首先訪問起點(diǎn)，然后依次訪問與該起點(diǎn)相關(guān)聯(lián)的每一個(gè)頂點(diǎn)，并以該關(guān)聯(lián)頂點(diǎn)為新的起點(diǎn)，繼續(xù)深度優(yōu)先遍歷。若圖中還有未被訪問的頂點(diǎn)，則換一個(gè)起點(diǎn)，繼續(xù)深度優(yōu)先遍歷；直到所有的頂點(diǎn)都被訪問。V1V2V3V4V5V6V7V8無(wú)向圖G3V1V2V3V4V5V6V7V8有向圖G4V1,V3,V6,V7,V2,V4,V8,V5V1,V2,V4,V8,V5,V3,V6,V7深度優(yōu)先遍歷：VoidDFSTravers(GRAPHG,v){For(v=0;v<G.vexnum;++v)visited[v]=FALSE;For(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}VoidDFS(GRAPHG,intv){visited[v]=TRUE;visitfunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w);if(!visited[w])DFS(G,w);}v13v2v3v4v54422123010101234^^無(wú)向圖G2鄰接表V3V1V4V5V2G2圖G2的深度優(yōu)先遍歷結(jié)果：V1,V4,V3,V5,V2DFSTraverse（G）{

T=￠;/*樹邊集開始為空*/count=1;/*先深編號(hào)計(jì)數(shù)器*/for(allv∈V)markv“new”while(thereexistsavertexv∈Vmarked“new”)search(v)}

voidsearch(v){dfn[v]=count;/*對(duì)v編號(hào)*/count=count+1;markv“old”/*訪問結(jié)點(diǎn)v*/for(eachvertexw∈L[v])if(wismarked“new”{add(v,w)toT;/*(v,w)是樹邊*/search(w);/*遞歸搜索*/}}輸入：L[v]表示無(wú)向圖G的關(guān)于v的鄰接表輸出：每個(gè)結(jié)點(diǎn)有先深編號(hào)的無(wú)向圖和樹邊集T2、廣度優(yōu)先搜索BFS(Breadth-Firstsearch)V1V2V3V4V5V6V7V8無(wú)向圖G3V1V2V3V4V5V6V7V8有向圖G4V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V3,V4,V5,V6,V7,V8

首先訪問起點(diǎn)，依次訪問與該起點(diǎn)相關(guān)聯(lián)的每一個(gè)鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，若圖中還有未被訪問的頂點(diǎn)，則換一個(gè)起點(diǎn)，繼續(xù)廣度優(yōu)先遍歷；直到所有的頂點(diǎn)都被訪問。VoidBFSTravers(GRAPHG,v){For(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueue(Q);For(v=0;v<G.vexnum;++v)if(!visited[v]){EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);visited[u]=TRUE;visit(u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w);if(!visited[w])EnQueue(Q,w);}}}v13v2v3v4v54422123010101234^^無(wú)向圖G2鄰接表V3V1V4V5V2G2圖G2的廣度優(yōu)先遍歷結(jié)果：V1,V4,V2,V3,V5Voidbsearch(v){MAKENULL(Q);bfn[v]=count;/*先廣編號(hào)*/count=count+1;markv“old”ENQUEUE(v,Q);/*v入隊(duì)*/while(!EMPTY(Q)){v=FRONT(Q);DEQUEUE(Q);for(eachw∈L[v]){bfn[w]=count;/*先廣編號(hào)*/count=count+1;markw“old”;ENQUEUE(w,Q);INSERT((v,w),T);}}/*樹邊入隊(duì)*/}輸入：L[v]表示無(wú)向圖G的關(guān)于v的鄰接表輸出：每個(gè)結(jié)點(diǎn)有先廣編號(hào)的無(wú)向圖和樹邊集T4.4圖與樹的聯(lián)系4.4.1先深生成森林和先廣生成森林abdecfg(a)abdecfg(b)abdecfg(c)樹邊(編號(hào)小->大)與非樹邊：回退邊/橫邊(編號(hào)大->小)先深（廣）搜索過程中，由樹邊和樹邊所連接的頂點(diǎn)組成的子圖，稱為圖的先深（廣）生成森林。無(wú)向連通圖通過先深（廣）搜索只能得到一個(gè)先深（廣）生成樹非連通圖則可得到多個(gè)生成樹連通子圖（連通分量）4.4.3最小生成樹4.4.2無(wú)向圖與開放樹[定義]

連通而無(wú)環(huán)路的無(wú)向圖稱作開放樹（FreeTree）開放樹的性質(zhì)：（1）具有n≥1個(gè)頂點(diǎn)的開放樹包含n-1條邊（2）如果在開放樹中任意加上一條邊，便得到一條回路(證明見教材P154～155)

設(shè)G=(V,E)是一個(gè)連通圖，E中每一條邊(u,v)的權(quán)為C(u,v)，也叫做邊長(zhǎng)。圖G的一株生成樹(spanningtree)是連接V中所有結(jié)點(diǎn)的一株開放樹。將生成樹中所有邊長(zhǎng)之總和稱為生成樹的價(jià)(cost)。使這個(gè)價(jià)最小的生成樹稱為圖G的最小生成樹(minimum-costspanningtree)。MST性質(zhì)

設(shè)G=(V,E)是一個(gè)連通圖，在E上定義一個(gè)權(quán)函數(shù)，且{(V1,T1),(V2,T2),…,(Vk,Tk)}是G的任意生成森林。令T=∪Ti(k>1)ki=1

又設(shè)e=(v,w)是E-T中這樣一條邊，其權(quán)C[v,w]最小，而且v∈V1和w∈V1。則圖G有一棵包含T∪{e}的生成樹，其價(jià)不大于包含T的任何生成樹的價(jià)。

假設(shè)N=(V,{E})是一個(gè)連通網(wǎng)，U是頂點(diǎn)V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，其中u∈U,v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。描述1：描述2：UV－Uuvu’v’MST性質(zhì)證明假設(shè)網(wǎng)N的任何一棵最小生成樹都不包含（u,v），設(shè)T是連通網(wǎng)上的一棵最小生成樹，當(dāng)將邊（u,v）加入到T中時(shí)，由生成樹的定義，T中必包含一條（u,v）的回路。另一方面，由于T是生成樹，則在T上必存在另一條邊（u’,v’），且u和u’、v和v’之間均有路徑相同。刪去邊(u’,v’)便可消去上述回路，同時(shí)得到另一棵最小生成樹T’。但因?yàn)?u,v)的代價(jià)不高于(u’,v’)，則T’的代價(jià)亦不高于T，T’是包含（u，v）的一棵最小生成樹。（a）V3V1V4V5V2V66515536462V3V1V4V5V2（c）V614V3V1V4V5V2（d）V6142V3V1V4V5V2（e）V61542V3V1V4V5V2（f）V615342求最小生成樹V3V1V4V5V2（b）V61UV-U１、求最小生成樹——Prim算法輸入：加權(quán)無(wú)向圖（無(wú)向網(wǎng)）G=(V,E)，其中v=(1,2,…,n).輸出：G的最小生成樹要點(diǎn)：引入集合U和T。U準(zhǔn)備結(jié)點(diǎn)集，T為樹邊集。初值U={1}，

T=￠。選擇有最小權(quán)的邊(u,v)，使u∈U,v∈(V-U),將v加入

U,（u,v）加入T。重復(fù)這一過程，直到U=V.voidprim(G,T){T=￠;U={1};while((U–V)!=￠){設(shè)(u,v)是使u∈U與v∈(V-U)且權(quán)最小的邊；

T=T∪{(u,v)};U=U∪{v};}};引入輔助向量：

CLOSEST[]和LOWCOSTCLOSEST[i]為U中的一個(gè)頂點(diǎn)則邊(i,CLOSEST[i])具有最小的權(quán)LOWCOST[i]集合如何實(shí)現(xiàn)？若頂點(diǎn)i∈U則LOWCOST[i]=INFINITYCLOSTST和LOWCOST的初值是多少？開始調(diào)整LOWCOST,對(duì)非集合U中的頂點(diǎn)jLOWCOST[j]=min(C[k][j],LOWCOST[j])CLOSEST[j]=k;i++結(jié)束LOWCOST[i]為鄰接矩陣C的第一行值CLOSEST[i]的初值均為1從LOWCOST[i]中求值最小的頂點(diǎn)

k(k,CLOSEST[k])為求得的一條邊將頂點(diǎn)k加入到集合U定義：CLOSEST[i]為U中的一個(gè)頂點(diǎn)邊(i,CLOSEST[i])具有最小的權(quán)LOWCOST[i]Prim算法流程圖i=2i<=nYesNoVoidPrim(C)詳見P135-136CosttypeC[n+1][n+1];{costtypeLOWCOST[n+1];intCLOSEST[n+1];inti,j,k;costtypemin;

for(i=2;i<=n;i++){LOWCOST[i]=C[1][i];CLOSEST[i]=1;}

賦初值

for(i=2;i<=n;i++)

{

min=LOWCOST[i];k=i;for(j=2;j<=n;j++)if(LOWCOST[j]<min){min=LOWCOST[j];k=j;}

求離U中某一頂點(diǎn)最近的頂點(diǎn)

Cout<<“(”<<k<<“,”<<CLOSEST[k]<<“)”<<end1;LOWCOST[k]=INFINITY;將k加入集合U

for(j=2;j<=n;j++)if(C[k][j]<LOWCOST[j]&&LOWCOST[j]!=INFINITY){LOWCOST[j]=C[k][j];CLOSEST[j]=k;}調(diào)整

}}CLOSEST[i]為U中的一個(gè)頂點(diǎn)邊(i,CLOSEST[i])具有最小的權(quán)LOWCOST[i]V3V1V4V5V2V66515536462C123456123456∞615∞∞6∞5∞3∞15∞5645∞5∞∞2∞36∞∞6∞∞426∞LOWCOST[i]i=123456123456--615∞-∞-5∞5645∞26∞5∞∞6∞∞∞∞3∞∞∞∞∞∞CLOSEST[i]i=123456123456--111113113331633316333162331622打印邊123456K(K,CLOSEST[K])3(3,1)6(6,3)4(4,6)2(2,3)5(5,2)for(j=2;j<=n;j++)if(C[k][j]<LOWCOST[j]&&LOWCOST[j]<INFINITY){LOWCOST[j]=C[k][j];CLOSEST[j]=k;}V3V1V4V5V2V66515536462[例]K=?min(LOWCOST[])CLOSEST[i]為U中的一個(gè)頂點(diǎn)邊(i,CLOSEST[i])具有最小的權(quán)LOWCOST[i]算法要點(diǎn)：

令T=(V,E),(V=1,2,3,…,n),c是關(guān)于E中每條邊的權(quán)函數(shù)1、T中每個(gè)頂點(diǎn)自身構(gòu)成一個(gè)連通分量；2、按照邊的權(quán)不減的順序，依次考查E中的每條邊；3、如果被考查的邊連接不同的分量中的兩個(gè)頂點(diǎn)，則合并兩個(gè)分量；4、如果被考查的邊連接同一個(gè)分量中的頂點(diǎn)，則放棄，避免環(huán)路；5、T中連通分量逐漸減少；當(dāng)T中的連通分量的個(gè)數(shù)為1時(shí)，說明V中的全部頂點(diǎn)通過E中權(quán)最小的那些邊，構(gòu)成了一個(gè)沒有環(huán)路的連通圖T，即為最小生成樹。２、求最小生成樹——Kruskal算法輸入：連通圖G=(V,E)，其中v=(1,2,…,n)，C是關(guān)于E中的每條弧的權(quán)。輸出：G的最小生成樹VoidKruskal(V,T){T=V;ncomp=n;/*結(jié)點(diǎn)個(gè)數(shù)*/while(ncomp>1){從E中取出刪除權(quán)最小的邊（v,u）;if(v和u屬于T中不同的連通分量）

{T=T∪{(v,u)}ncomp--;}}}1264537182023122515851067412645371812158564egfhdbca2212121(b)egfhdbca2212121(c)egfhdbca23212412213(a)*4.5無(wú)向圖的雙連通性(Biconnectivity)P1374.4.1無(wú)向圖的雙連通分量設(shè)G=(V,E)[定義]

假若在刪去頂點(diǎn)v以及和v相關(guān)聯(lián)的邊之后，將圖的一個(gè)連同分量分割成兩個(gè)或兩個(gè)以上的連同分量，則稱該結(jié)點(diǎn)為關(guān)節(jié)點(diǎn)。abdecfg(a)bdecfg(b)abdefg(c)[定義]

若對(duì)V中每個(gè)不同的三元組v,w,a；在v和w之間都存在一條不包含a的路，就說G是雙連通的（Biconnected）先深搜索和先深編號(hào)的作用:

通過是否遇到回退邊，即可確定是否有環(huán)路。說V中的點(diǎn)a是一個(gè)關(guān)節(jié)點(diǎn)，若V中有結(jié)點(diǎn)v和w，使得v,w,a

各不相同且v

和w

之間的每條路都包含a

。

雙連通的無(wú)向圖是連通的，但連通的無(wú)向圖未必雙連通。一個(gè)連通的無(wú)向圖是雙連通的，當(dāng)且僅當(dāng)它沒有關(guān)節(jié)點(diǎn)。[定義]

若

e1=e2

或者有一條環(huán)路包含e1又包含

e2

，

則稱邊e1

和e2

是等價(jià)的。[定義]

設(shè)Vi

是

Ei

中各邊所連接的點(diǎn)集（1≤i≤k）,每個(gè)圖

Gi=(Vi,Ei)

叫做

G

的一個(gè)雙連通分量。雙連通分量的性質(zhì)：

性質(zhì)1：

Gi

是雙連通的（1≤i≤k）

性質(zhì)2：對(duì)所有的i≠j,Vi∩Vj

最多包含一個(gè)點(diǎn)

性質(zhì)3：

v

是G的關(guān)節(jié)點(diǎn)，當(dāng)且僅當(dāng)v∈Vi∩Vj(i≠j)雙連通圖的研究意義：如通訊網(wǎng)絡(luò)。上述等價(jià)關(guān)系將E分成等價(jià)類E1,E2,…,Ek,兩條不同的邊屬于同一個(gè)類的充要條件是它們?cè)谕粋€(gè)環(huán)路上。V1V2V3V4V5V6V9V7V8無(wú)向圖和它的雙連通分量圖G圖G的雙連通分量V1V2V3（1）V4V6（4）V2V4V5（2）V6V9V7V8（3）4.4.2求關(guān)節(jié)點(diǎn)—對(duì)圖進(jìn)行一次先深搜索便可求出所有的關(guān)節(jié)點(diǎn)若生成樹的根有兩株或兩株以上子樹，則此根結(jié)點(diǎn)必為關(guān)節(jié)點(diǎn)

（第一類關(guān)節(jié)點(diǎn)）。因?yàn)閳D中不存在連接不同子樹中頂點(diǎn)的邊，因此，若刪去根頂點(diǎn)，生成樹變成生成森林。若生成樹中非葉頂點(diǎn)v，其某株子樹的根和子樹中的其它結(jié)點(diǎn)均沒有指向v的祖先的回退邊，則v是關(guān)節(jié)點(diǎn)（第二類關(guān)節(jié)點(diǎn)）。因?yàn)閯h去v，則其子樹和圖的其它部分被分割開來1abdecfg234567由先深生成樹可得出兩類關(guān)節(jié)點(diǎn)的特性：gcafedb定義low[v]：

設(shè)對(duì)連通圖G＝（V,E）進(jìn)行先深搜索的先深編號(hào)

為dfn[v]，產(chǎn)生的先深生成樹為S＝（V,T），B是

回退邊之集。對(duì)每個(gè)頂點(diǎn)v，low[v]定義如下：gcafedbabdecfg12345671111555dfn

lowlow[v]=mindfn[v],dfn[w],low[y](v,w)∈B，w

是頂點(diǎn)v

在先深生成樹上有回退邊連接的祖先結(jié)點(diǎn)；(v,y)∈T，y

是頂點(diǎn)v

在先深生成樹上的孩子頂點(diǎn)Low[v]取頂點(diǎn)v和w的深度優(yōu)先編號(hào)的較小者，其中的w是從v點(diǎn)沿著零條或多條樹邊到v的后代x，之后沿著任意一條回退邊(x,w)所能達(dá)到的任何頂點(diǎn)算法4.5求無(wú)向圖的雙連通分量輸入：連通的無(wú)向圖G=(V,E)。L[v]表示關(guān)于v的鄰接表。輸出：G的所有雙連通分量，每個(gè)連通分量由一序列的邊組成。算法要點(diǎn)：1.計(jì)算先深編號(hào)：對(duì)圖進(jìn)行先深搜索，計(jì)算每個(gè)結(jié)點(diǎn)v的先深編號(hào)

dfn[v]，形成先深生成樹S＝（V,T）。2.計(jì)算low[v]：在先深生成樹上按后根順序進(jìn)行計(jì)算每個(gè)頂點(diǎn)v的

low[v]，low[v]取下述三個(gè)結(jié)點(diǎn)中的最小者：

(1)dfn[v]:(2)dfn[w]:凡是有回退邊（v,w）的任何結(jié)點(diǎn)w；

(3)low[y]:對(duì)v的任何兒子(樹邊)y。3.求關(guān)節(jié)點(diǎn)：

(1)樹根是關(guān)節(jié)點(diǎn)，當(dāng)且僅當(dāng)它有兩個(gè)或兩個(gè)以上的兒子

（第一類關(guān)節(jié)點(diǎn)）；

(2)非樹根結(jié)點(diǎn)v是關(guān)節(jié)點(diǎn)當(dāng)且僅當(dāng)v有某個(gè)兒子y，使

low[y]≥dfn[v]（第二類關(guān)節(jié)點(diǎn)）。VoidsearchB(v){(1)makev“old”;(2)dfn[v]=count;(3)count++;(4)low[v]=dfn[v];(5)for(eachw∈L[v])(6)if(wismarked”new”)(7){add(v,w)toT;(8)father[w]=v;//w是v的兒子

(9)searchB(w);(10)if(low[w]>=dfn[v])Abiconnectedcomponenthasbeenfound;(11)low[v]=min(low[v],low[w]);}(12)elseif(wisnotfather[v])//(v,w)是回退邊

(13)low[v]=min(low[v],dfn[w]);}調(diào)用過程：T=￠;count=1;for(allv∈V)makev“new”;searchB(v0);//v0為任意頂點(diǎn)*4.6有向圖的搜索DFS和BFS搜索在有向圖和無(wú)向圖中的區(qū)別？有向圖搜索：樹邊、向前邊、回退邊、和橫邊1、若dfn[v]<dfn[w]，則(v,w)是樹邊或向前邊；

此時(shí)，visited[v]=“old”,visited[w]=“new”,(v,w)為樹邊

visited[v]=“old”,visited[w]=“old”,(v,w)為向前邊2、若dfn[v]>dfn[w]，則(v,w)是回退邊或橫邊；

當(dāng)產(chǎn)生樹邊(i,j)時(shí)，同時(shí)記下j的父親：father[j]=i,于是對(duì)圖中任一條邊(v,w)，當(dāng)visited[v]=“old”,visited[w]=“old”且dfn[v]>dfn[w]時(shí)，由結(jié)點(diǎn)v沿著樹邊向上(father中)查找w（可能直到根）；若找到w,則(v,w)是回退邊，否則是橫邊ABECDGHF(a)AECDGHFB12345678圖(a)先深生成森林ABECD(b)ABECD12345圖(b)先廣生成森林*4.7強(qiáng)連通性有向圖的強(qiáng)連通分量是滿足下列要求的最大子集：對(duì)任意兩個(gè)頂點(diǎn)x

和y

，都存在一條有向路從x

到y(tǒng)

，也存在一條有向路從y

到x。設(shè)G=（V,E）是一個(gè)有向圖，稱頂點(diǎn)v,w∈V是等價(jià)的，要么v=w；要么從頂點(diǎn)v

到w

有一條有向路，并且從頂點(diǎn)w

到v

也有一條有向路。[定義]設(shè)Ei（1≤i≤r）是頭、尾均在Vi

中的邊集,則Gi

=(Vi,Ei)稱為G的一個(gè)強(qiáng)連通分量，簡(jiǎn)稱強(qiáng)分量。[定義]上述等價(jià)關(guān)系將V分成若干個(gè)等價(jià)類V1，V2,…,Vr強(qiáng)連通圖：只有一個(gè)強(qiáng)分量的有向圖稱為強(qiáng)連通圖。分支橫邊：不在任何強(qiáng)連通分支（量）中的邊，如：a→d,c→d注：每個(gè)結(jié)點(diǎn)都是在某個(gè)強(qiáng)連通分支中出現(xiàn)，但有些邊可能不在任何強(qiáng)分支中。歸約圖：用強(qiáng)分量代表頂點(diǎn)，用分支橫邊代表有向邊的圖稱為原圖的歸約圖。顯然，歸約圖是一個(gè)不存在環(huán)路的有向圖，它表示了強(qiáng)分量之間的連通性。adcb(a)adcb(b)a,b,cd歸約圖adcb(a)eabcd(b)e54321abcd(c)e54321算法:P145，(step1---step4)求強(qiáng)連通圖的實(shí)例4.8拓?fù)浞诸惤o定一個(gè)無(wú)環(huán)路有向圖G=(V,E),各結(jié)點(diǎn)的編號(hào)為v=(1,2,…,n)。要求對(duì)每一個(gè)結(jié)點(diǎn)i

重新進(jìn)行編號(hào)，使得若i

是j的前導(dǎo)，則有Label[i]<label[j]。即拓?fù)浞诸愂菍o(wú)環(huán)路有向圖排成一個(gè)線性序列，使當(dāng)從結(jié)點(diǎn)i

到結(jié)點(diǎn)j存在一條邊，則在線性序列中，將i排在j

的前面。*+***+e+*+ecdcbb+cdcd*+**+*+ecbcd((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)有向無(wú)環(huán)圖及其應(yīng)用課程代號(hào)課程名稱先修課代號(hào)1計(jì)算機(jī)原理82編譯原理4,53操作系統(tǒng)4,54程序設(shè)計(jì)無(wú)5數(shù)據(jù)結(jié)構(gòu)4,66離散數(shù)學(xué)97形式語(yǔ)言68電路基礎(chǔ)99高等數(shù)學(xué)無(wú)10計(jì)算機(jī)網(wǎng)絡(luò)1例：12435678910v1v2v4v3v6v5v1v2v4v3v5v2v4v3v5v2v3v5v2v5v5可輸出結(jié)點(diǎn)的入度為零，刪去該結(jié)點(diǎn)，并將與該頂點(diǎn)相鄰的頂點(diǎn)的入度減1。V6V1V4V3V2V5021230入度V1V2V3V4V5v6top=0(a)021231入度(b)021121入度(c)014021入度(d)044011入度(e)044011入度(f)toptoptoptoptopv6→v1→v3→v2→v4→044001入度(f)topv5→044001入度(g)top=0v14v2v3v4v555322^^v654021230^^^^v1v2v4v3v6v561^top鏈棧的初始狀態(tài)進(jìn)棧：ID[i]=top;top=i;退棧：i=top;top=ID[top]021230入度ID[i]123456top=0014021入度top021231入度ID[i]123456top=661^top算法主要步驟：計(jì)算每個(gè)頂點(diǎn)i的入度ID[i]；for(i=1;i<=n;i++)//初始化鏈棧；

if(ID[i]==0){ID[i]=top;top=i;}for(i=1;i<=n;i++){輸出top指針指向的頂點(diǎn)；

k=top;top=ID[top];

頂點(diǎn)k的每一個(gè)鄰接點(diǎn)j的入度-1if(ID[j]==0){ID[j]=top;top=j;}}進(jìn)棧：ID[i]=top;top=i;退棧：i=top;top=ID[top]StatusTopologicalsort(ALGRAPHG){FindInDegree(G,indegree);MakeNUlLL(S);for(v=0;v<n;++v)if(!indegree[v])push(v,S);count=0;while(!EMPTY(S)){v=pop(S);printf(v);++count;for(鄰接于v的每個(gè)頂點(diǎn)w){if(!(--indegree[w]))push(S,w);}}if(count<n)cout<<“圖中有環(huán)路”;elsereturnOK;}算法一：應(yīng)用棧StatusTopologicalsort(L){QUEUEQ;MakeNUlLL(Q);for(v=1;v<=n;++v)if(indegree[v]=0)ENQUEUE(v,Q);nodes=0;while(!EMPTY(Q)){v=FRONT(Q);DEQUEUE(Q);cout<<v;nodes++;for(鄰接于v的每個(gè)頂點(diǎn)w)if(!(--indegree[w]))ENQUEUE(w,Q);}if(nodes<n)cout<<“圖中有環(huán)路”;}算法二：應(yīng)用隊(duì)列算法三：DFS遍歷生成拓?fù)湫蛄蠽oidtopodfs(v){PUSH(v,S);mark[v]=TRUE;for(L[v]中的每一個(gè)頂點(diǎn)w)doif(mark[w]=FALSE)topodfs(w);printf(top(S));POP(S);}Voiddfs-topo(GRAPHL){MAKENULL(S);for(u=1;u<=n;u++)make[u]=FALSE;for(u=1;u<=n;u++)if(!mark[u])topodfs(u);}思想：借助棧，在DFS中，把第一次遇到的頂點(diǎn)入棧，到達(dá)某一頂點(diǎn)遞歸返回，從棧中彈出頂點(diǎn)并輸出。AOE網(wǎng)（ActivityOnEdgeNetwork）

在帶權(quán)的有向圖中，用結(jié)點(diǎn)表示事件，用邊表示活動(dòng)，邊上權(quán)表示活動(dòng)的開銷（如持續(xù)時(shí)間），則稱此有向圖為邊表示活動(dòng)的網(wǎng)絡(luò),簡(jiǎn)稱AOE網(wǎng)。4.9關(guān)鍵路徑v7源點(diǎn)起始點(diǎn)v1v4v3v2v5v6v9a1=6a6=2a3=5a2=4a5=1a4=1a7=9a8=7a9=4a11=4a10=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v8AOE網(wǎng)的性質(zhì)只有在某個(gè)頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊代表的活動(dòng)才能開始;只有在進(jìn)入某一頂點(diǎn)的各有向邊代表的活動(dòng)已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生；表示實(shí)際工程計(jì)劃的AOE網(wǎng)應(yīng)該是無(wú)環(huán)的，并且存在唯一的入度為0的開始頂點(diǎn)（源點(diǎn)）和唯一的出度為0的結(jié)束點(diǎn)（匯點(diǎn)）。v7源點(diǎn)起始點(diǎn)v1v4v3v2v5v6v9a1=6a6=2a3=5a2=4a5=1a4=1a7=9a8=7a9=4a11=4a10=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v8AOE網(wǎng)研究的主要問題：如果用AOE網(wǎng)表示一項(xiàng)工程，那么僅僅考慮各個(gè)子工程之間的優(yōu)先關(guān)系還不夠，更多地是關(guān)心整個(gè)工程完成的最短時(shí)間是多少，哪些活動(dòng)的延遲將影響整個(gè)工程進(jìn)度,而加速這些活動(dòng)能否提高整個(gè)工程的效率,因此AOE網(wǎng)有待研究的問題是:(1)完成整個(gè)工程至少需要多少時(shí)間？(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？v7源點(diǎn)起始點(diǎn)v1v4v3v2v5v6v9a1=6a6=2a3=5a2=4a5=1a4=1a7=9a8=7a9=4a11=4a10=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v8路徑長(zhǎng)度、關(guān)鍵路徑、關(guān)鍵活動(dòng)：路徑長(zhǎng)度：是指從源點(diǎn)到匯點(diǎn)路徑上所有活動(dòng)的持續(xù)時(shí)間之和。關(guān)鍵路徑：在AOE網(wǎng)中，由于有些活動(dòng)可以并行，所以完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最大路徑長(zhǎng)度。因此，把從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑。一個(gè)AOE中，關(guān)鍵路徑可能不只一條。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。v7源點(diǎn)起始點(diǎn)v1v4v3v2v5v6v9a1=6a6=2a3=5a2=4a5=1a4=1a7=9a8=7a9=4a11=4a10=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v8①事件Vj

的最早可能發(fā)生時(shí)間VE(j)

是從源點(diǎn)V1到頂點(diǎn)Vj的最長(zhǎng)路徑長(zhǎng)度。②活動(dòng)ai的最早可能開始時(shí)間E(k)

設(shè)活動(dòng)ai在邊<Vj,Vk>上,則E(i)也是從源點(diǎn)V1到頂點(diǎn)Vj

的最長(zhǎng)路徑長(zhǎng)度。這是因?yàn)槭录j發(fā)生表明以Vj為起點(diǎn)的所有活動(dòng)ai可以立即開始。因此,

E(i)=VE(j)…………..(1)關(guān)鍵路徑和關(guān)鍵活動(dòng)性質(zhì)分析：（與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量）v7源點(diǎn)起始點(diǎn)v1v4v3v2v5v6v9a1=6a6=2a3=5a2=4a5=1a4=1a7=9a8=7a9=4a11=4a10=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v8③事件Vk的最遲發(fā)生時(shí)間VL(k)

是在保證匯點(diǎn)Vn在VE(n)時(shí)刻完成的前提下，事件Vk的允許的最遲開始時(shí)間。在不推遲工期的情況下，一個(gè)事件最遲發(fā)生時(shí)間VL(k)應(yīng)該等于匯點(diǎn)的最早發(fā)生時(shí)間VE(n)減去從Vk到Vn的最大路徑長(zhǎng)度。v7源點(diǎn)起始點(diǎn)v1v4v3v2v5v6v9a1=6a6=2a3=5a2=4a5=1a4=1a7=9a8=7a9=4a11=4a10=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v8④活動(dòng)ai的最遲允許開始時(shí)間L(i)

是指在不會(huì)引起工期延誤的前提下，活動(dòng)ai允許的最遲開始時(shí)間。因?yàn)槭录k發(fā)生表明以Vk為終點(diǎn)的入邊所表示的所有活動(dòng)均已完成，所以事件Vk的最遲發(fā)生時(shí)間VL(k)也是所有以Vk為終點(diǎn)的入邊<Vj,Vk>所表示的活動(dòng)ai可以最遲完成時(shí)間。顯然，為不推遲工期，活動(dòng)ai的最遲開始時(shí)間L(i)應(yīng)該是ai的最遲完成時(shí)間VL(k)減去ai的持續(xù)時(shí)間，即

L(i)=VL(k)-ACT[j][k]…………..(2)

其中,ACT[j][k]是活動(dòng)ai的持續(xù)時(shí)間（<Vj,Vk>上的權(quán)）。VjVkai⑤時(shí)間余量L(i)-E(i)

L(i)-E(i)表示活動(dòng)ak的最早可能開始時(shí)間和最遲允許開始時(shí)間的時(shí)間余量。關(guān)鍵路徑上的活動(dòng)都滿足：L(i)=E(i)…………..(3)

L(i)=E(i)表示活動(dòng)是沒有時(shí)間余量的關(guān)鍵活動(dòng)。

由上述分析知，為找出關(guān)鍵活動(dòng)，需要求各個(gè)活動(dòng)的E(i)與L(i)，以判別一個(gè)活動(dòng)ai是否滿足L(i)=E(i)。E(i)和L(i)可有公式(1)和(2)。而VE(k)

和VL(k)可由拓?fù)浞诸愃惴ǖ玫?。利用拓?fù)浞诸愃惴ㄇ箨P(guān)鍵路徑和關(guān)鍵活動(dòng)。Step1(前進(jìn)階段)：從源點(diǎn)V1出發(fā)，令VE(1)=0，按拓?fù)湫蛄写涡蚯蟪銎溆喔黜旤c(diǎn)事件的最早發(fā)生時(shí)間:利用拓?fù)浞诸愃惴ㄇ箨P(guān)鍵路徑和關(guān)鍵活動(dòng)

其中T是以頂點(diǎn)Vk為尾的所有邊的頭頂點(diǎn)的集合(2≤k≤n)如果網(wǎng)中有回路，不能求出關(guān)鍵路徑則算法中止；否則轉(zhuǎn)Step2。其中S是以頂點(diǎn)Vj為頭的所有邊的尾頂點(diǎn)的集合(2≤j≤n-1)j∈TVE(k)=max{VE(j)+ACT[j][k]

}Step2(回退階段)：從匯點(diǎn)Vn出發(fā)，令VL(n)=VE(n)，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最晚發(fā)生時(shí)間：k∈SVL(j)=min{VL(k)+ACT[j][k]}Step3：求每一項(xiàng)活動(dòng)ai的最早開始時(shí)間:

E(i)=VE(j)

最晚開始時(shí)間:

L(i)=VL(k)-ACT[j][k]

若某條邊滿足E(i)=L(i)，則它是關(guān)鍵活動(dòng)。為了簡(jiǎn)化算法,可以在求關(guān)鍵路徑之前已經(jīng)對(duì)各頂點(diǎn)實(shí)現(xiàn)拓?fù)渑判?并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號(hào)。不是任意一個(gè)關(guān)鍵活動(dòng)的加速一定能使整個(gè)工程提前。想使整個(gè)工程提前，要考慮各個(gè)關(guān)鍵路徑上所有關(guān)鍵活動(dòng)。例1:活動(dòng)e(i)l(i)l(i)-e(i)a1a2a3a4a5a6a7a8a9a10a1100002203366046258377077071031616014140注：Ve(i)：事件最早可能發(fā)生時(shí)間源點(diǎn)到達(dá)該事件的最長(zhǎng)路經(jīng)Vl(i)：事件最遲發(fā)生時(shí)間

VE(n)-maxLik

e(i)：活動(dòng)最早可能開始時(shí)間

Ve(活動(dòng)起點(diǎn))

l(i)：活動(dòng)最遲允許開始時(shí)間

Vl(活動(dòng)終點(diǎn))-ai

事件vevlv1v2v3v4v5v6v7v8v90066465877710161614141818v7源點(diǎn)起始點(diǎn)v1v4v3v2v5v6v9a1=6a6=2a3=5a2=4a5=1a4=1a7=9a8=7a9=4a11=4a10=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v8123654a1=3a2=2a4=3a3=2a5=4a6=1a7=2a8=3例2:頂點(diǎn)Ve(i)Vl(i)活動(dòng)e(i)l(i)l(i)-e(i)123456a1a2a3a4a5a6a7a8032668042678003326621044276510110103注：事件最早可能發(fā)生時(shí)間Ve(i)

源點(diǎn)到達(dá)該事件的最長(zhǎng)路經(jīng)事件最遲發(fā)生時(shí)間Vl(i)VE(n)-maxLik活動(dòng)最早可能開始時(shí)間e(i)Ve(活動(dòng)起點(diǎn))活動(dòng)最遲允許開始時(shí)間l(i)

Vl(活動(dòng)終點(diǎn))-ai

4.10單源最短路徑D[1]D[2]D[3]D[4]D[5]∞10∞30100D∞10∞30100∞∞50∞∞∞∞∞2010∞∞20∞60∞∞∞∞∞C集合S={1}{1,2,3,4,5}20124351010030105060V0Dijkstra算法基本思想：集合S的初值為S={1}D為各頂點(diǎn)當(dāng)前最小路徑從V-S中選擇頂點(diǎn)w，使D[w]的值最小并將w加入集合S，則w的最短路徑已求出。調(diào)整其他各結(jié)點(diǎn)的當(dāng)前最小路徑

D[k]=min{D[k],D[w]+C[w][k]}直到S中包含所有頂點(diǎn)12435101003010502060V0循環(huán)SwD[2]D[3]D[4]D[5]初態(tài){1}-10∞301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060算法的逐步求精過程：算法：VoidDijkstra(G){S={1};for(i=2;i<=n;i++)D[i]=C[1][i];for(i=1;i<n;i++){從V-S中選出一個(gè)頂點(diǎn)w,使D[w]最小；

S=S+{w};for(V-S中的每一個(gè)頂點(diǎn)v)D[v]=min(D[v],D[w]+C[w][v]);}}算法：VoidDijkstra(GRAPHG,costtypeD[MAXVEX+1]){intS[MAXVEX+1];for(i=1;i<=n;i++){D[i]=G[1][i];S[i]=FALSE;}S[1]=TRUE;for(i=1;i<n;i++){w=mincost(D,S);S[w]=TRUE;for(v=2;v<=n;n++)if(S[v]!=TRUE){sum=D[w]+G[w][v];if(sum<D[v])D[v]=sum;}}}intmincost(D,S){temp=INFINITY;w=2;for(i=2;i<=n;i++)if(!S[i]&&D[i]<temp){temp=D[i];w=i;}returnw;}最小路徑經(jīng)過哪些點(diǎn)？算法：VoidDijkstra(GRAPHG,costtypeD[MAXVEX+1]){intS[MAXVEX+1],P[MAXVEX+1];for(i=1;i<=n;i++){D[i]=G[1][i];S[i]=FALSE;P[i]=1;}S[1]=TRUE;for(i=1;i<n;i++){w=mincost(D,S);S[w]=TRUE;for(v=2;v<=n;n++)if(S[v]!=TRUE){sum=D[w]+G[w][v];if(sum<D[v]){D[v]=sum;p[v]=w;

}}}}P[1]P[2]P[3]P[4]P[5]11413P循環(huán)SwD[2]D[3]D[4]D[5]D[6]初態(tài){1}-∞

10∞301001{1,3}3∞106030