第5.4連通圖與生成樹(shù)

PAGEPAGE3 圖的結(jié)第五 5.1—圖的概念三圖的基本術(shù)語(yǔ)§5.1的基本概G由兩個(gè)集合V,E構(gòu)成，記作例V1={v0E1={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v有序?qū)?lt;vi,vj有序?qū)?lt;vi,vj4§5.1的基本概V2={v0,v1,v2,v3,v4無(wú)序?qū)o(wú)序?qū)2圖5§5.1的基本概 例1交通圖（公路、鐵路）例3通訊線路圖例4邊：各道工序之間的順序關(guān) §7.1的基本概e三圖e1鄰接點(diǎn)：邊e=(v,u)，則稱(chēng)頂點(diǎn)v、u相鄰接關(guān)聯(lián)邊：邊e=(v,u),則稱(chēng)邊e關(guān)連頂點(diǎn)v、u2頂點(diǎn)的度、入度、出度頂點(diǎn)V的度=與V頂點(diǎn)V的度=V的出度+V的入度設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為圖的=（每條邊對(duì)圖的所有頂點(diǎn)的度數(shù)和“貢獻(xiàn)”2度 §5.1的基本概3路徑、回?zé)o向圖G=（V，E）中的頂點(diǎn)序列v1,v2,…,vk,若i=1,2,…k-1)vv1uvk則稱(chēng)該序列是從頂點(diǎn)v到頂點(diǎn)u路徑；若v=u例有向圖D=（V，E）中的頂點(diǎn)序列v1,v2,…,vk,若<vi,vi+1>E(i=1,2,…k-1),vv1uvk則稱(chēng)該序列是從頂點(diǎn)v到頂點(diǎn)u例在圖1中，V0,V1,V2,V3是V0到V3的路徑；V0,V1,V2,V3,V0路；在圖2中，V0,V2,V3是有向無(wú)向8簡(jiǎn)單路徑和簡(jiǎn)單例在圖1中，V0,V1,V2,V3V0,V1,V2,V4,V1無(wú)向

有向連通圖（強(qiáng)連通圖在無(wú)（有）向圖G=<V,Ev、u都存在從v到u的路徑，則稱(chēng)G是連通圖（強(qiáng)連通圖） 圖 圖子 V，E1E1關(guān)聯(lián)的頂點(diǎn)都在V1中，則稱(chēng)G1是G例(b)、(c)(a)的子 連通分量（強(qiáng)連通分量無(wú)向圖G的極大連通子圖稱(chēng)為G

§5.1的基本概G連通子圖，將G有向圖D的極大強(qiáng)連通子圖稱(chēng)為D強(qiáng)連通分連通連通G1的生成生成

§5.1的基本概包含無(wú)向圖G所有頂點(diǎn)的的極小連通子圖稱(chēng)為G極小連通子圖意思是：該子圖是G若T是G的生成樹(shù)當(dāng)且僅當(dāng)TT是G的連通子圖T包含G的所有四圖的基本操 第五 5.2圖的結(jié)構(gòu) 鄰接 鏈 鄰接多重§5.2圖的結(jié)圖的結(jié)構(gòu)至少要保存兩類(lèi)信息頂點(diǎn)的數(shù)頂點(diǎn)間的關(guān)G=<VG=<VE>是圖V={v0,v1,v2…vn-1},設(shè)頂點(diǎn)數(shù)據(jù)為它鄰接矩圖的鄰接矩陣表示法（AdjacencyMatrix）也稱(chēng)作數(shù)組表示一個(gè)是用于頂點(diǎn)信息的一維數(shù)組；另一個(gè)用于圖 若圖是一個(gè)具有n個(gè)頂點(diǎn)的無(wú)權(quán)圖，的鄰接矩陣是n×n矩陣：

j]

若<vivj>或(vivj)—數(shù)組表示法(

§5.2圖 結(jié)鄰接矩陣：G的鄰接矩陣是滿(mǎn)足如下條件的n1若(vi,vj)E0101010101010111010001100010110000000011000若圖是一個(gè)有n個(gè)頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的n×n矩陣：

j]

若<vivj>或(vi反例如：一個(gè)有向網(wǎng)N,其鄰接矩陣55427896155無(wú)向圖數(shù)組表示法特點(diǎn)無(wú)向圖鄰接矩陣是對(duì)稱(chēng)矩陣，同一條邊表示了兩次頂點(diǎn)vi的度：等于二維數(shù)組i行（或列）中1的個(gè)數(shù)

§5.2圖的結(jié)判斷兩頂點(diǎn)v、u是否為鄰接點(diǎn)：只需判二維數(shù)組對(duì)應(yīng)分量是否為頂點(diǎn)不變，在圖中增加、刪除邊：只需對(duì)二維數(shù)組對(duì)應(yīng)分量賦值1或清數(shù)組表示法的空數(shù)組表示法的空只與圖的頂點(diǎn)數(shù)有1010010110100110圖的基本操作

§5.2圖的結(jié)求無(wú)向圖某頂點(diǎn)vi的度(或有向圖中vi的出度)。A[I,0]A[I,n-1]中的非0個(gè)數(shù)，即數(shù)組A中第i行的非0元素的個(gè)數(shù)求有向圖某頂點(diǎn)vi度A[0,i]到An-1,i中的非0個(gè)數(shù)，即數(shù)組A第i列的非0元素的個(gè)數(shù)檢測(cè)圖中的總邊數(shù)。掃描整個(gè)數(shù)組A，統(tǒng)計(jì)出數(shù)組中非0元素的個(gè)數(shù)。無(wú)的總邊數(shù)為非0元素個(gè)數(shù)的一半，而有向圖的總弧數(shù)為非0元素個(gè)010101010101010111010001100000000100§5.2圖的結(jié)該結(jié)點(diǎn)表該結(jié)點(diǎn)表示（ViVj）,其中的1是在一維數(shù)組中的位在一維 鄰接表是圖的鏈?zhǔn)浇Y(jié)無(wú)向圖的鄰接頂點(diǎn)：通常按順序?qū)㈨旤c(diǎn)數(shù)據(jù)例下 例21234m- 圖的鄰接表類(lèi)型constMAX_VERTEX_NUM=

§5.2圖的結(jié)typedef ode //弧結(jié)點(diǎn)的結(jié)intadjvex; //該弧所指向的頂點(diǎn)的位置 ode*nextarc; //指向下一條弧的指針VRTypeweight; //與弧相關(guān)的權(quán)值，無(wú)權(quán)則為0InfoType //指向該弧相關(guān)信息的指}typedefstructVNode //頂點(diǎn)結(jié)點(diǎn)的結(jié)VertexType //頂點(diǎn)信ode //指向第一條依附該頂點(diǎn)的}typedefstruct //圖的鄰接表結(jié)構(gòu)定AdjList //頂點(diǎn)數(shù)int //圖的當(dāng)前頂點(diǎn)數(shù)和弧GraphKind //圖的種類(lèi)標(biāo) }無(wú)向圖的鄰接表的特 §5.2圖的結(jié)在G鄰接表中，同一條邊對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)(v->w,w頂點(diǎn)v的度：等于v對(duì)應(yīng)線性鏈表的長(zhǎng)度判定兩頂點(diǎn)v，u是否鄰接：要看v對(duì)應(yīng)線性鏈表中有無(wú)應(yīng)的結(jié)點(diǎn)4)適用于邊稀疏的鄰接表鄰接表的空間代與圖的邊及頂點(diǎn)數(shù)均有為2234m-有向圖的鄰接表和逆鄰接有向圖的鄰接例例

§5.2圖的結(jié)下 113300m-

類(lèi)似于無(wú)向圖的2所不同的是2以同一頂點(diǎn)為起用線性鏈 類(lèi)似于有向圖的所類(lèi)似于有向圖的所不同的是例例03 03 0 02 2m-第五次作§5.2圖的結(jié)三、鏈表 該圖的鏈如flashheadvexheadvex表示弧頭頂點(diǎn)在圖中的位置tailvex表示弧尾頂點(diǎn)在圖中的位置hlink指向與此弧的弧頭相同的下一條弧圖的鏈表

(a)鏈表弧結(jié)點(diǎn)結(jié)構(gòu)示意firstin域(鏈域)用于指向以該頂點(diǎn)作為弧頭的第一個(gè)firstin域(鏈域)用于指向以該頂點(diǎn)作為弧頭的第一個(gè)弧頂點(diǎn)

firstout域(鏈域)用于指向以該頂點(diǎn)作為弧尾的第一個(gè)弧頂點(diǎn)tlink指向與此弧的弧尾相同的下一條弧(b)鏈表頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)示意43221432211323433441441圖圖有向圖G1的鏈圖的鏈表結(jié)構(gòu)形式化定義如下＃defineMAX-VERTEX- /*最多頂點(diǎn)個(gè)數(shù)typedefenum{DG,DN,UDG,UDN} /*圖的種類(lèi)typedefstruct ode{ ode typedefstruct /*頂點(diǎn)信息 typedef vertex［MAX-VERTEX- /*圖的頂點(diǎn)數(shù)和弧數(shù) /*圖的種類(lèi) } /*圖的鏈表表示法(Orthogonal建立一個(gè)有向圖的鏈表的算法如下voidCrtOrthList（OrthList/*從終端輸入n個(gè)頂點(diǎn)的信息和e條弧的信息，以建立一個(gè)有向圖的鏈表{scanf(″%d,%d&n,&e);/*從鍵盤(pán)輸入圖的頂點(diǎn)個(gè)數(shù)和弧的個(gè)數(shù)for(i=0;i<n;{scanf(″%c″,g.vertex［i］.firstin=NULL；g.vertex［i］}for(k=0;k<e;{scanf(″%c,%c″,&vt,i=LocateVertex（g，vt）；j= p->tailvex=i；p-p->tlink=g.vertex［i］.firstout；g.vertex［i］.firstoutp->hlink=g.vertex［j］.firstin；g.vertex［j］.firstin}}/*CrtOrthList四、鄰接多重表 §5.2圖 結(jié)行的操作帶來(lái)不便。以下面的無(wú)向圖為例，當(dāng)從頂點(diǎn)A出發(fā)了邊(A,E)之后，為了下次不再對(duì)這條邊進(jìn)行，就需要找到表示這條邊的另一個(gè)結(jié)點(diǎn)加問(wèn)標(biāo)志。表如flash標(biāo)志域：可用以標(biāo)記該條邊是否被搜索標(biāo)志域：可用以標(biāo)記該條邊是否被搜索過(guò)ivex的邊ivex：是該邊依附的一個(gè)頂點(diǎn)在圖 jvex：是該邊依附的另一個(gè)頂點(diǎn)在圖jlink(鏈域)：用于指向下一條依附于頂?shù)奈恢眯蛱?hào)

中的位置序號(hào)data域用于頂點(diǎn)的名字與頂點(diǎn)有data域用于頂點(diǎn)的名字與頂點(diǎn)有關(guān)的信息，如

jvex的邊f(xié)ifirstedge域用于指向第一條依附于該頂點(diǎn)的邊dat鄰接多重表中頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu) 鄰接多重表的結(jié)點(diǎn)結(jié)typedefstructEdgeNodeintmark,ivex,structEdgeNode typedefstruct{VertexDatadata;EdgeNode*firstedge;typedef /*圖的頂點(diǎn)數(shù)和弧數(shù) /*圖的種類(lèi) /*基于圖的鄰接多重表表示法(AdjacencyMulti-54354345無(wú)向圖G2的鄰接多重§5.2圖的結(jié)在不同的結(jié)構(gòu)下，實(shí)現(xiàn)的效率 無(wú)向鍵盤(pán)輸入數(shù)據(jù)，建立一個(gè)無(wú)向圖的鄰接矩陣，并輸出該鄰接矩在無(wú)向圖的鄰接矩陣的基礎(chǔ)上計(jì)算各頂點(diǎn)的度，并輸出有向鍵盤(pán)輸入數(shù)據(jù)，建立一個(gè)有向圖的鄰接表，并輸出該鄰接表在有向圖的鄰接表的基礎(chǔ)上計(jì)算各頂點(diǎn)的度，并輸出§5.3

都進(jìn)行一次且僅進(jìn)行一次。如何確保每個(gè)頂點(diǎn)都被到如何確保每個(gè)頂點(diǎn)只被一次§5.3的圖的遍歷：從圖的某頂點(diǎn)出發(fā)，圖中所有頂點(diǎn)，并且每個(gè)頂點(diǎn)僅一次。為保證每一個(gè)頂點(diǎn)只被一次，必須對(duì)頂點(diǎn)進(jìn)行標(biāo)記，頂點(diǎn)vi未被，值為0；當(dāng)vi已被，則值為1圖的遍歷有兩種遍歷方法（它們對(duì)無(wú)向圖，有向圖都適用§5.3的度優(yōu)先遍從圖中某頂點(diǎn)v1）頂點(diǎn)2）依次從v的未被的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷例求圖G以V0為起點(diǎn)的的深度優(yōu)先遍歷例（1）

這是序列所經(jīng)過(guò)的路由于由于沒(méi)有規(guī)

深度優(yōu)先遍從圖中某頂點(diǎn)v（1）頂點(diǎn)

§5.3的 依次從v的未 的鄰接點(diǎn) 出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷直到與v有路徑相連的頂點(diǎn)全部 時(shí)還有頂點(diǎn)未被問(wèn)到，則另取一未被（1）根結(jié)點(diǎn)先序遍歷左子樹(shù)先序遍歷右子樹(shù)

圖的遍歷樹(shù)的遍歷有什么不如果將圖頂點(diǎn)的鄰接是不是很類(lèi)似§5.3的深度優(yōu)先遍歷算調(diào)用深度優(yōu)先遍歷算法的主函bool //附設(shè)標(biāo)識(shí)數(shù)voidDFSTraverse(Graph{//對(duì)圖G作深度優(yōu)先遍for(v=0;v<G.vexnum;visited[v]= //標(biāo)識(shí)數(shù)組初始for(v=0;v<G.vexnum;if(!visited[v])DFS(G,v);//對(duì)尚未的頂點(diǎn)調(diào)用}深度優(yōu)先遍歷算法flash演§5.3的圖深度優(yōu)先遍歷voidDFS(GraphG,int{//從頂點(diǎn)v出發(fā)遞歸地深度優(yōu)先遍歷圖visited[v]=TRUE; //頂點(diǎn)for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)//對(duì)v的尚未過(guò)的鄰接頂點(diǎn)w遞歸調(diào)用if(!visited[w])DFS(G,}（1）頂點(diǎn)v并標(biāo)記頂點(diǎn)v為已若頂點(diǎn)vj尚未被，則深度優(yōu)先遍歷遞歸頂點(diǎn)12356

§5.3的1 212553 43401 01

該圖的深度優(yōu)先二廣度優(yōu)先遍歷（類(lèi)似于樹(shù)的按層遍歷）從圖中某個(gè)未被過(guò)的頂點(diǎn)vi出發(fā)：1）頂點(diǎn)vi；

§5.3的2）vi的所有未被的鄰接點(diǎn)w1,w2,…wk依次從這些鄰接點(diǎn)出發(fā)，它們的所有未被的鄰接點(diǎn)依此類(lèi)推，直到圖中所有過(guò)的頂點(diǎn)的鄰接點(diǎn)都被例求圖G的以V0起點(diǎn)的的廣度優(yōu)先序由由于沒(méi)有規(guī)鄰接點(diǎn)的順序廣度優(yōu)先序列不是唯一廣度優(yōu)先遍歷算從圖中某頂點(diǎn)vi出發(fā)1）頂點(diǎn)vi；（容易實(shí)現(xiàn)

§5.3的2）vi的所有未被的鄰接點(diǎn)w1,w2,…wk；（容易實(shí)現(xiàn)3）依次從這些鄰接點(diǎn)（在步驟2）的頂點(diǎn)）出發(fā)，它們的所有未被的鄰接點(diǎn);依此類(lèi)推，直到圖中所有過(guò)的頂點(diǎn)為實(shí)現(xiàn)3），需要保存在步驟(2）中的頂點(diǎn)，而且這些在廣度優(yōu)先遍歷算在廣度優(yōu)先遍歷算法中需設(shè)置一隊(duì)列保存的頂點(diǎn)并控制遍歷頂點(diǎn)的順序§5.3的廣度優(yōu)先遍從圖中某頂點(diǎn)v1）頂點(diǎn)v2）v的所有未被的鄰接點(diǎn)w1,w2,…wk3）依次從這些鄰接點(diǎn)出發(fā)，它們的所有未被的鄰接點(diǎn)依此類(lèi)推，直到圖中所有過(guò)的頂點(diǎn)的鄰接點(diǎn)都被V0V1V2 V5V6廣廣度優(yōu)先遍歷算法flash演voidBFSTraverse(MGraph{//對(duì)以數(shù)組表示的圖G進(jìn)行廣度優(yōu)先搜索遍bool //附設(shè)標(biāo)識(shí)數(shù)Queue 附設(shè)隊(duì)for(v=0;v<G.vexnum;++v)visited[v]=FALSE; 設(shè)置空隊(duì)Qfor(v=0;v<G.vexnum;++v)if({//從每一個(gè)未被的頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜visited[v]=TRUE; //圖中第v個(gè)頂EnQueue(Q v入隊(duì)while{DeQueue(Q //隊(duì)頭元素出隊(duì)并置為for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)if(!visited[w]{visited[wTRUE 圖中w個(gè)頂EnQueue(Q, //當(dāng) 的頂點(diǎn)w入隊(duì)列}//}//}//if 圖的廣度優(yōu)先遍歷算法需要一個(gè)隊(duì)列以保持過(guò)的頂點(diǎn)的順序，以按順 這些頂點(diǎn)鄰接頂點(diǎn)。連通圖的廣度優(yōu)先遍歷算法為（1）初始頂點(diǎn)v并標(biāo)記頂點(diǎn)v為已頂點(diǎn)v入隊(duì)列當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行，否則算法結(jié)束出隊(duì)列取得隊(duì)頭頂點(diǎn)查找頂點(diǎn)u的第一個(gè)鄰接頂點(diǎn)若頂點(diǎn)u的鄰接頂點(diǎn)w不存在，則轉(zhuǎn)到步驟（3），否則執(zhí)行后序句①若頂點(diǎn)w尚未被，則頂點(diǎn)w并標(biāo)記頂點(diǎn)w為已②頂點(diǎn)w入隊(duì)列③查找頂點(diǎn)u的的下一個(gè)鄰接頂點(diǎn)，轉(zhuǎn)到步驟（6）§§5.4 無(wú)向圖的生成

§5.4生成樹(shù)是通圖G的一個(gè)極小的連通子圖。包含圖G的有頂點(diǎn)，但只有n-1條邊，并且是連通的深度優(yōu)先生成 廣度優(yōu)先生成最小若有通的無(wú)向圖G，有n個(gè)頂點(diǎn)，并且它的邊是值的。在G上構(gòu)造最小生成樹(shù)G’–它的n-1條邊的權(quán)值之和

§5.4成例 例如何求連通圖最小生成樹(shù)要在n個(gè)城市間建立通信網(wǎng)，如如何求連通圖最小生成樹(shù)求解: 連通6個(gè)城市且

§5.4小的生成二算法加頂點(diǎn)算法P175算法7-算法基本步設(shè)G=（V，E）為一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)的連通網(wǎng)絡(luò)，T=（U，TE）為構(gòu)造的生成樹(shù)（1）初始時(shí)（2）在所有uU 、vV-U 的邊（u,v）中選擇一條權(quán)值最小的邊，V(u0,v0)加入TE，同時(shí)將vV重復(fù)(2)、（3），直到U=V為止算法的flash§5.4小的生成U={V0 U={V0,V2 U={11 4 1 4

1 4

1 4 U={V0,V2,V5,V3 U={V0,V2,V5,V3,V1}U={V0,V2,V5,V3,V194§5.4小的生成三算 加邊的算基本步設(shè)G=（V，E）為一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)的連通網(wǎng)絡(luò)，最小生成樹(shù)的初狀態(tài)為有n個(gè)頂點(diǎn)但無(wú)邊的非連通T=（V，）將E，則將其加入T中，否則，將其棄循環(huán)至有N-1條邊算法flash 算法的時(shí)復(fù)度為O(n，與網(wǎng)中的邊數(shù)無(wú)關(guān)，因 算法的時(shí)間復(fù)雜度為O(eloge（為網(wǎng)中邊的數(shù)目），因此適合于求邊稀疏的網(wǎng)的最小生成樹(shù)。33221243第六次作§5.5有向無(wú)環(huán)圖及應(yīng)用—AOV網(wǎng)撲排序鍵路有向無(wú)環(huán)圖：沒(méi)有回路的有向

§5.5應(yīng)用：工程流程、生產(chǎn)過(guò)程中各道工序的流程、程序流程、課程的AOV網(wǎng)（activityonvertexnet用頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)的順序關(guān)系的有向圖稱(chēng)為AOV 某工程可分為7個(gè)子工程，若用頂點(diǎn)表示子工程（也稱(chēng)活動(dòng)），用例 課程流程

§5.5某校計(jì)算機(jī)專(zhuān)業(yè)課程流程可用AOV網(wǎng)表示。其中頂點(diǎn)：表示課程（也稱(chēng)動(dòng)），?。罕硎菊n程間的先修關(guān)系課 課程名 程序設(shè)

如何安排施工計(jì)劃 如何安排教學(xué)計(jì) 離散數(shù) 數(shù)據(jù)結(jié) 匯編語(yǔ) 算法分 計(jì)算機(jī)體

數(shù)值分

撲排1拓?fù)渑?/p>

§5.5對(duì)工程問(wèn)題，人們至少關(guān)心如下兩類(lèi)問(wèn)題程進(jìn)度的關(guān)鍵子工程§5.5一個(gè)可行的施工計(jì)劃為：V0,V1,V2,一個(gè)可行的學(xué)習(xí)計(jì)劃為可行的計(jì)劃的特點(diǎn)：若在流程圖中頂點(diǎn)v是頂點(diǎn)u的前趨，則§5.5拓?fù)湫蛄校河邢驁DD的一個(gè)頂點(diǎn)序列稱(chēng)作一個(gè)拓?fù)湫蛄腥绻撔蛄兄腥蝺身旤c(diǎn)v、u，若在D中v是u前趨，則在拓?fù)湫蛄兄衯也是u前。拓?fù)渑判颍簩⒂邢驁D中頂點(diǎn)排成拓?fù)?拓?fù)渑判虻膽?yīng)安排施工計(jì)劃（如上 判斷工程流程的是否合如何判斷AOV網(wǎng)（有向圖

進(jìn)行拓?fù)渑?§5.5 拓?fù)渑判蚍椒ㄔ谟邢驁D選一無(wú)前趨的頂點(diǎn)v，輸出從有向圖中刪除v及以v為尾的孤拓?fù)渑判蛩惴≒182算法7-§5.5 拓?fù)渑判蛩惴≒182算法7-拓?fù)渑判蚍椒ǖ牧硪环N描述(等價(jià)描述選擇一入度0v，輸出將v鄰接到的頂點(diǎn)的入度減重復(fù)1、2直到輸出全部頂點(diǎn)或有向圖沒(méi)有入度為0的頂點(diǎn)拓?fù)渑判蛏婕暗臄?shù)據(jù)和操作數(shù)據(jù)：有向圖，頂點(diǎn)的入度操作（1）擇一入度0頂點(diǎn)v，輸出（2）v鄰接到的頂u的入度減在有向圖選一無(wú)前趨的頂點(diǎn)在有向圖選一無(wú)前趨的頂點(diǎn)v，輸出從有向圖中刪除v及以v為尾的孤重復(fù)1、2、直至輸出全部頂點(diǎn)或有向圖中不存在無(wú)前趨頂算法的flash55532555323440416266263 為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?對(duì)于給定的有向圖,采用鄰接表作為結(jié)構(gòu),為每個(gè)頂點(diǎn)設(shè)立一個(gè)鏈表,每個(gè)鏈表有一個(gè)表頭結(jié)點(diǎn),這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組,表頭結(jié)點(diǎn)中增加一個(gè)存typedef /*表頭結(jié)點(diǎn)類(lèi)型 /*頂點(diǎn)信息intcount; ode*firstarc; }voidTopSort(VNodeadj[],int inti,j;intSt[MAXV],top=-1;/*棧St的指針為top*/ode*p;forif /*入度為0的頂點(diǎn)入棧 top++; whiletop>- /*棧不為空時(shí)循環(huán) printf("%d",i);while j=p->adjvex;adj[j].count--if{top++;St[top]=j;p=p }三AOE網(wǎng)與關(guān)鍵路

§5.5AOE網(wǎng)：用邊表示活動(dòng)，頂點(diǎn)表示事件，權(quán)表示活動(dòng)持續(xù)的時(shí)間的網(wǎng)對(duì)工程人們關(guān)心兩類(lèi)問(wèn)題的關(guān)鍵子工程

頂點(diǎn)表示事邊表示活

AOE事件Vi發(fā)生表ak可以開(kāi)

事件Vj發(fā)生表ak已結(jié)§5.5網(wǎng)、E網(wǎng)，都能表示工程各子工程的流程，一個(gè)用頂點(diǎn)表示活動(dòng)，一個(gè)用邊表示活動(dòng)，但網(wǎng)側(cè)重表示活動(dòng)的前后次序，E網(wǎng)除表示活E網(wǎng)解決工程所需最短時(shí)間及哪些子工程拖延會(huì)影響整個(gè)工程按時(shí)完成等問(wèn)題。實(shí)際應(yīng)用中采關(guān)鍵路徑：最長(zhǎng)的路徑V1->V3->V4-相關(guān)概念關(guān)鍵路徑：事件Vj的最早發(fā)生時(shí)間ve(j：從源點(diǎn)1到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度。這個(gè)時(shí)間決定了所有以Vj的最早開(kāi)始時(shí)間。事件Vj的最遲發(fā)生時(shí)間vl(j：在不影響整個(gè)工期的情況下，事件Vj必須發(fā)生的時(shí)間。活動(dòng)ai的最遲開(kāi)始時(shí)間l(i):在不推遲整個(gè)工程完工的前提下，活動(dòng)ai最遲必須開(kāi)始進(jìn)行的時(shí)間，即l(i)=vl(k)-dut(〈j,k〉)，其中dut(〈j,k〉)為活動(dòng)ai的持續(xù)時(shí)間。關(guān)鍵活動(dòng)：最早開(kāi)始時(shí)間=最遲開(kāi)始時(shí)間的活動(dòng)， l(i)=e(i)的活動(dòng)事件Viak事件Vjak例如，上圖是一個(gè)有8例如，上圖是一個(gè)有8項(xiàng)活動(dòng)的AOE-網(wǎng)。其中有6個(gè)事8,VV,a 如，活動(dòng)a1需要3天，活動(dòng)a4需要3天等等 事件vj的最早發(fā)生時(shí)間

§5.5 ve[j]=從源點(diǎn)到頂點(diǎn)vj的最長(zhǎng)路徑的長(zhǎng)i事件vj的最遲發(fā)生時(shí)間vl[j]=Min{vl(k)- vl[j]=vl[n]-從頂點(diǎn)vj到終點(diǎn)的最長(zhǎng)路徑的長(zhǎng)活動(dòng)ak的最早開(kāi)始時(shí)間設(shè)ak=<i,j> 活動(dòng)ak的最晚開(kāi)始時(shí)間e1[k]=vl[j]-活動(dòng)ak的延遲時(shí)間diff[k]=e1[k]- 把活動(dòng)ai的最晚開(kāi)始時(shí)間e1[i]與最早開(kāi)始時(shí)間ee[i]之差定義為活動(dòng)ai的延遲時(shí)計(jì)算過(guò)程flash§5.5對(duì)于活動(dòng)ai，若e1[i]-事件事件最早發(fā)生時(shí)最晚發(fā)生時(shí)003422666788活動(dòng)最早發(fā)最晚發(fā)生時(shí)010034342225666 BBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDH活動(dòng)a10：e(10)=ve(F)=16,l(10)=vl(I)- BBFAECIGDH§5.6最短路徑（一、最短路徑問(wèn)交通咨詢(xún)系統(tǒng)、通訊網(wǎng)、計(jì)算機(jī)網(wǎng)絡(luò)常要尋找兩結(jié)點(diǎn)間最短路交通咨詢(xún)系統(tǒng)：A到B最短路計(jì)算機(jī)網(wǎng)發(fā)送節(jié)省費(fèi)用A到B沿最短路徑傳路徑長(zhǎng)度：路徑上邊路徑上邊的權(quán)值之最短路徑：兩結(jié)點(diǎn)間權(quán)值之和最小的路例：求V0到V4最短路V0到V4路徑：V0 V0V0V1V0V2V3V0V2V3V1

§5.6短二從某源點(diǎn)到其余各點(diǎn)的最短路帶權(quán)值的有向圖的單源最短路徑問(wèn)如何如何求從某源到其余各點(diǎn)的最短路徑1算法Dijkstra算法的基本思

§5.6短按路徑長(zhǎng)度遞增順序求最短路徑算法。與求最小生成樹(shù)的普里姆算法類(lèi)Dijkstra算法的基本步設(shè)V0是起始源點(diǎn)，U已求得最短路徑終點(diǎn)集合。V-U=未確定最短路徑的頂?shù)募跏糢長(zhǎng)度最短的最短路徑是從v0下一條長(zhǎng)度最短的路徑ViVU，先求出V0到Vi中間只U中結(jié)點(diǎn)的最短路徑②上述最短路徑中長(zhǎng)度最小者即為下一條長(zhǎng)度最短的路徑③將所求最短路徑的終點(diǎn)加入U(xiǎn)中重復(fù)2）直到求出所有的最短路路徑終點(diǎn)

-

-

-

-路徑終點(diǎn)

（V0,v2）

a

-

-路徑終點(diǎn)

）

（V0,V4,v3）路徑終點(diǎn)

-

-

--路徑終點(diǎn)

（V0,V4,v5（V0,v4,v3,V5（V0,v4,v3,V5）最短路的終

{V0,V2,V4}{V0,V2,V4,V3}

§5.6短始終無(wú)(c)第(c)第一次求得的結(jié)果第二次求得的結(jié)果05 105 182430 1 (a)一個(gè)有向網(wǎng)點(diǎn)00341823030341824303403418243 1 (e)第三次求得的結(jié) 第四次求得的結(jié)果圖5- Dijkstra算 §5.6最短路voiddijstra(intcost[][N],intv{intfor(i=0i<Ni++dist[i]=cost[v][i//初始dist[v]=-for(i=0;i<N;{j=mincost(dist);//找非0、非負(fù)且最小的dist[j]if(j==0);break;dist[j]=-dist[j];//vj并入U(xiǎn)中for(k=0;k<N;k調(diào)整dist[k] vk是尚未到達(dá)的終if(-dist[k]=-dis