1、第八章 圖,圖的定義 圖的存儲結(jié)構(gòu) 圖的遍歷 圖的應(yīng)用,8.1 圖的定義和術(shù)語,1. 圖 有向圖（Digragh） 無向圖（Undigraph）,8.1 圖的定義和術(shù)語,有向圖（Digragh） G=（V，A） 其中，V為頂點(diǎn)的有窮非空集合 A為頂點(diǎn)之間的關(guān)系集合,G1=（V，A） V=v1, v2, v3, v4 A=, , , 其中表示從x到y(tǒng)的一條弧（arc），A為弧集合，x為弧尾（tail），y為弧頭（head),8.1 圖的定義和術(shù)語,無向圖（Undigraph） G=(V,E) 其中，V同有向圖，E為頂點(diǎn)之間的關(guān)系集合， E為邊集合,G2=（V，A） V=v1, v2, v3, v

2、4, v5 E=(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5) 其中，(x, y)表示x與y之間的一條連線，稱為邊（edge）,8.1 圖的定義和術(shù)語,設(shè)n為頂點(diǎn)數(shù)，e為邊或弧的條數(shù) 對無向圖有：0=e=n(n-1)/2 有向圖有：0=e=n(n-1),證明：每個頂點(diǎn)至多有n-1條邊與其它的n-1個頂點(diǎn)相 連，則n個頂點(diǎn)至多有n(n-1)條邊。但每條邊連 接2個頂點(diǎn)，故最多為n(n-1)/2,8.1 圖的定義和術(shù)語,2. 完全圖 邊達(dá)到最大的圖,無向完全圖：邊數(shù)為n(n-1)/2的無向圖 有向完全圖：弧數(shù)為n(n-1)的有向圖,

3、權(quán)：與圖的邊或弧相關(guān)的數(shù) 網(wǎng)：邊或弧上帶有權(quán)值的圖,8.1 圖的定義和術(shù)語,3. 頂點(diǎn)的度 TD（V） 無向圖：為依附于頂點(diǎn)V的邊數(shù) 有向圖：等于以頂點(diǎn)V為弧頭的弧數(shù)（稱為V的 入度，記 為ID（V）與以頂點(diǎn)V為弧尾的弧數(shù)（稱為V 的出度，記為OD（V）之和。即： TD（V）=ID（V）+OD（V）,無向圖 n e= 1/2（TD(vi)） i=1,結(jié)論：,有向圖 n n e= ID(vi)=OD(vi) i=1 i=1,無向圖的度數(shù)為依附于頂點(diǎn)v 的邊數(shù)；有向圖的度數(shù)等于以 頂點(diǎn)v 為弧頭的弧數(shù)與以頂點(diǎn)v 為弧尾的弧數(shù)之和,8.1 圖的定義和術(shù)語,4. 路徑 無向圖：頂點(diǎn)v到v的路徑是一個頂

4、點(diǎn)序列（v=vi0, vi1, , vim=v） 其中，（vij-1,vij ）E, 1=j=m 有向圖： 頂點(diǎn)v 到v的路徑是有向的頂點(diǎn)序列（v=vi0, vi1, , vim=v） 其中，（vij-1,vij ）A, 1=j=m,幾個概念： 路徑長度：路徑上邊或弧的數(shù)目 回路或環(huán)：首尾頂點(diǎn)相同的路徑，稱為回路或環(huán)。即： （v=vi0, vi1, , vim=v=v） 簡單路徑：路徑中不含相同頂點(diǎn)的路徑 簡單回路：除首尾頂點(diǎn)外，路徑中不含相同頂點(diǎn)的回路,5. 連通 頂點(diǎn)連通：若頂點(diǎn)v到頂點(diǎn)v有路徑，則稱頂點(diǎn)v與v是連通的 連 通 圖 ：包括無向連通圖和有向連通圖 無向圖：若圖中任意兩個頂點(diǎn)v

5、i,vj都是連通的，則稱該圖 是連通圖(vivj) 有向圖：若圖中任意兩個頂點(diǎn)vi,vj，都存在從vi到vj和從 vj到vi的路徑，則稱該有向圖為強(qiáng)連通圖(vivj) 連通分量： 無向圖：無向圖中極大連通子圖，稱為連通分量 有向圖：有向圖中極大強(qiáng)連通子圖，稱為強(qiáng)連通分量,8.1 圖的定義和術(shù)語,5. 連通 連通分量：,G1有兩個強(qiáng)連通分量,8.1 圖的定義和術(shù)語,6. 生成樹 定義：設(shè)無向圖G是含有n個頂點(diǎn)的連通圖， 則圖G的生成樹是 含有n個頂點(diǎn)，且只有n-1條邊的連通子圖 三要素： n個頂點(diǎn) n-1條邊 連通,極小連通子圖，若再加一條邊，必構(gòu)成環(huán),8.2 圖的存儲結(jié)構(gòu),圖有數(shù)組、鄰接表、鄰

6、接多重表和十字鏈表等表示方法,一、數(shù)組表示法（鄰接矩陣）,設(shè)圖G=（V，E）有n個頂點(diǎn)，則G的鄰接矩陣定義為n階方陣A。 其中：Ai，j= 1 若（ vi，vj）或 E，ij 0 其它,無向圖的鄰接矩陣為對稱矩陣,8.2 圖的存儲結(jié)構(gòu),特點(diǎn)：判定兩個頂點(diǎn)Vi與Vj是否關(guān)聯(lián),只需判Ai,j是否為1 頂點(diǎn)的度容易求得:,8.2 圖的存儲結(jié)構(gòu),網(wǎng)的鄰接矩陣 定義為： Ai，j= Wij，若（Vi，Vj）或E ，其它,如圖：,8.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,1. 無向圖鄰接表,對圖中每個頂點(diǎn)Vi建立一個單鏈表，鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊，每個鏈表結(jié)點(diǎn)為兩個域：

7、,其中：鄰接點(diǎn)域（adjvex）記載與頂點(diǎn)Vi鄰接的頂點(diǎn)信息； 鏈域（nextarc）指向下一個與頂點(diǎn)Vi鄰接的鄰接的鏈表p結(jié)點(diǎn),每個鏈表附設(shè)一個頭結(jié)點(diǎn)，頭結(jié)點(diǎn)結(jié)構(gòu)為：,其中：vexdata存放頂點(diǎn)信息（姓名、編號等）； fristarc指向鏈表的第一個結(jié)點(diǎn)。,8.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,如圖G2的鄰接表為：,特點(diǎn)：設(shè)無向圖中頂點(diǎn)數(shù)為n，邊數(shù)為e， 則它的鄰接表需要n個頭結(jié)點(diǎn)和2e個表結(jié)點(diǎn)。 頂點(diǎn)Vi的度 TD（Vi）=鏈表i中的表結(jié)點(diǎn)數(shù)。,8.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,2. 有向圖鄰接表,與無向圖的鄰接表結(jié)構(gòu)一樣。只是

8、在第i條鏈表上的結(jié)點(diǎn)是以Vi為 弧尾的各個弧頭頂點(diǎn),特點(diǎn)：1. n個頂點(diǎn)，e條弧的有向圖，需n個表頭結(jié)點(diǎn)，e 個表結(jié)點(diǎn) 2. 第i條鏈表上的結(jié)點(diǎn)數(shù)，為Vi的出度 （求頂點(diǎn)的出度易，求入度難）,如圖G1的鄰接表為：,8.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,3. 有向圖逆鄰接表,與無向圖的鄰接表結(jié)構(gòu)一樣。只是在第i條鏈表上的結(jié)點(diǎn)是以Vi為 弧頭的各個弧尾頂點(diǎn),此時，第i條鏈表上的結(jié)點(diǎn)數(shù)，為Vi的入度,如圖G1的逆鄰接表為：,8.2 圖的存儲結(jié)構(gòu),三、十字鏈表（orthogonal list）,十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來的一種有向圖鏈?zhǔn)酱鎯Y(jié)構(gòu),1. 結(jié)點(diǎn)

9、結(jié)構(gòu),有向圖的每一條弧有一個弧結(jié)點(diǎn)，每一個頂點(diǎn)必有一個頂點(diǎn)結(jié)點(diǎn)， 其結(jié)構(gòu)為：,8.2 圖的存儲結(jié)構(gòu),2. 整體結(jié)構(gòu),通過hlink將弧頭相同的弧連在一個鏈表上； 通過tlink將弧尾相同的弧連在一個鏈表上 而hlink鏈和tlink鏈的頭結(jié)點(diǎn)就是頂點(diǎn)結(jié)點(diǎn),3. 例 G1的十字鏈表為：,8.2 圖的存儲結(jié)構(gòu),4. 特點(diǎn)：, 頂點(diǎn)結(jié)點(diǎn)數(shù)=頂點(diǎn)數(shù) 弧結(jié)點(diǎn)數(shù)=弧的條數(shù) 求入度：從頂點(diǎn)Vi的firstin出發(fā)，沿著弧結(jié)點(diǎn)中的hlink所經(jīng)過的弧結(jié)點(diǎn)數(shù)。 求出度：從頂點(diǎn)Vi的firstout出發(fā)，沿著弧結(jié)點(diǎn)中的tlink所經(jīng)過的弧結(jié)點(diǎn)數(shù)。,8.2 圖的存儲結(jié)構(gòu),四、鄰接多重表,鄰接多重表是無向圖的另一種鏈

10、式存儲結(jié)構(gòu)。,圖的每一條邊有一個邊結(jié)點(diǎn)，邊結(jié)點(diǎn)的結(jié)構(gòu)為：,每一個頂點(diǎn)有一個頂點(diǎn)結(jié)點(diǎn)，頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)為：,其中：ivex 和jvex為該邊所依附的兩個頂點(diǎn)。 ilink指向下一條依附于頂點(diǎn)ivex的邊。 jlink指向下一條依附于頂點(diǎn)jvex 的邊。 data存放頂點(diǎn)的信息。 firstedge指向第一條依附于該頂點(diǎn)的邊結(jié)點(diǎn)。,8.2 圖的存儲結(jié)構(gòu),四、鄰接多重表,如圖G2的鄰接多重表:,8.2 圖的存儲結(jié)構(gòu),四、鄰接多重表,如圖G2的鄰接多重表:,特點(diǎn)：頂點(diǎn)結(jié)點(diǎn)數(shù)為n，邊結(jié)點(diǎn)數(shù)為e； 對需要得到邊的兩個頂點(diǎn)的一類操作很方便 （如刪除一條邊，判一條邊是否已訪問）。,8.3 圖的遍歷,從圖中某個頂點(diǎn)

11、出發(fā)，沿路徑使圖中每個頂點(diǎn)被 訪問且僅被訪問一次的過程，稱為遍歷圖。,兩種常用遍歷圖的方法,深度優(yōu)先搜索（DFS）,廣度優(yōu)先搜索(BFS),8.3 圖的遍歷,一、深度優(yōu)先搜索（depth-first-search),1. 深度優(yōu)先搜索法遍歷圖的過程為：,訪問指定的某頂點(diǎn)V，將V作為當(dāng)前頂點(diǎn) 將該頂點(diǎn)作為當(dāng)前頂點(diǎn)，訪問當(dāng)前頂點(diǎn)的下一未被訪問過的鄰接點(diǎn) 重復(fù)2，直到當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪問點(diǎn)。 沿搜索路徑回退，退到尚有鄰接點(diǎn)未被訪問過的某結(jié)點(diǎn)，將該結(jié)點(diǎn) 作為當(dāng)前結(jié)點(diǎn)，重復(fù)以上步驟，直到所有頂點(diǎn)被訪問過的為止,8.3 圖的遍歷,一、深度優(yōu)先搜索（depth-first-search),如圖G4：

12、,8.3 圖的遍歷,一、深度優(yōu)先搜索（depth-first-search),2. 深度優(yōu)先搜索遞歸過程：,幾點(diǎn)說明：,FIRSTADJvex(g,V)和NEXTADJvex(g,V,w）函數(shù)的實現(xiàn)與圖的 具體存儲結(jié)構(gòu)有關(guān),8.3 圖的遍歷,一、深度優(yōu)先搜索（depth-first-search),2. 深度優(yōu)先搜索遞歸過程：,VOID traver(Graph g, Status (*visit) (int v ) VisitFunc=visit ; FOR (V=0 ; vG.vexnum ; +v ) visitedV=false; /作未訪問標(biāo)記 FOR (V=0 ; vG.vexnu

13、m ; +v ) IF (! visitedV) dfs(g,V) ; /dfs是以Vi 為出發(fā)點(diǎn)，遍歷一個連通分量 Void dfs(Graph g, int v) visitedV=true ; VisitFunc (v) ; /訪問第v個接點(diǎn) for (w=FIRSTADJ(g,V); W ;W=nextadjvex(G,v,w) /找V 的第一個鄰接點(diǎn) IF (! visitedw) dfs(g,w); /遞歸調(diào)用 ,8.3 圖的遍歷,2. 深度優(yōu)先搜索遞歸過程：圖若采用鄰接表存儲,Int FIRSTADJ(graph g,int v) /找與v鄰接的第一個頂點(diǎn),不存在返回0 p=ad

14、jlistv.firstarc; IF (!p) RETURN(0) ELSE RETURN (p-adjvex) Void NEXTADJ( graph g , int v , int w) /找V 的w之后的下一鄰接點(diǎn),不存在返回0 p=adjlistv.firstarc; WHILE (p AND p-adjvex!=w ) p= p-nextarc; /將移動指針定位到w IF (!p | !p-nextarc) RETURN(0) ELSE RETURN(p-nextarc-adjvex) ,8.3 圖的遍歷,2. 深度優(yōu)先搜索遞歸過程：,VOID traver(Graph g, B

15、oolean visitedvtxptr) FOR (V=0; V g.vexmum ; +V ) visitedV=false; FOR (V=0; Vg.vexnum ; +V) IF (! visitedV ) dfs(g,V) /dfs是以V 為出發(fā)點(diǎn)，遍歷一個連通分量 VOID dfs(Graph g , vtxptr V ) visit(V); visitedV=true; w=FIRSTADJvex(g,V); /找V 的第一個鄰接點(diǎn) WHILE (w ) IF (! visitedw) dfs(g,w); w=NEXTADJvex(g,V,w) /找V 的w之后的下一鄰接點(diǎn) ,

16、思考：traver調(diào)用 dfs的次數(shù)由什么決定？ 圖若采用鄰接矩陣存儲,編寫相應(yīng)的FIRSTADJvex(g,V)和NEXTADJvex(g,V,w),8.3 圖的遍歷,二、廣度優(yōu)先搜索（breadth-first-search),首先訪問指定頂點(diǎn)v0，將v0作為當(dāng)前頂點(diǎn); 訪問當(dāng)前頂點(diǎn)的所有未訪問過的鄰接點(diǎn)， 并依次將訪問的這些鄰接點(diǎn)作為當(dāng)前頂點(diǎn); 重復(fù)2， 直到所有頂點(diǎn)被訪問為止。,對右圖廣度優(yōu)先搜索，訪問頂點(diǎn)序列為： V1 V2 V3 V4 V5 V6 V7 V8,8.3 圖的遍歷,廣度優(yōu)先搜索算法：,VOID bfs(graph g, status (*visit)(int v) fo

17、r (v=0;vg.vexnum; +v) visitedv=false ; INIQUEUE(Q); for (v=0; vg.vexnum; +v) if (!visitedv) /v未訪問 visitedv=true ; visite(v) ; ENQUEUE(Q,V); /找與v鄰接的第一個頂點(diǎn),不存在返回0 WHILE (!QUEUEEMPTY (Q) DEQUEUE(Q,U) ; /隊頭元素出隊并置為u FOR (W=FIRSTADJVEX(g,U);W ;W=NEXTADJVEX(G,U,W) IF (!visitedw) /w為u的尚為訪問的鄰接點(diǎn) visitedw=true;

18、 visit(w); ENQUEWE(Q,w)； /if /while /找V 的w之后的下一鄰接點(diǎn) /if /bfs,8.4 最小生成樹,一、最小生成樹概念 1. 設(shè)無向連通圖G=（V，E）， 其子圖G=（V，T）滿足： V(G)=V(G) n個頂點(diǎn) G是連通的 G中無回路 則G是G的生成樹,8.4 最小生成樹,具有n個頂點(diǎn)的無向連通圖G 其任一生成G恰好含n-1條邊 生成樹不一定唯一，如,4個頂點(diǎn)選擇3條邊有 如下5種形狀(54= 20種): 其中16種為生成樹,（保證了連通）,生成樹代價,對圖中每條邊賦于一個權(quán)值（代價），則構(gòu)成一個網(wǎng)， 網(wǎng)的生成樹G=(V，T)的代價是T中各邊的權(quán)值之和

19、， 最小生成樹就是網(wǎng)上所有可能的生成樹中，代價最小的一類生成樹。 最小生成樹也不一定唯一。,8.4 最小生成樹,思考：要求每兩個城市（頂點(diǎn)）間都有路徑,最小生成樹的實用例子很多,例1：,N臺計算機(jī)之間建立通訊網(wǎng),頂點(diǎn)表示computer,邊表示通訊線,權(quán)值表示通訊線的代價（通訊 線長度，computer間距離等）,要求：, n臺計算機(jī)中的任何兩臺能通過網(wǎng)進(jìn)行通訊； 使總的代價最小。-求最小生成樹T,8.4 最小生成樹,最小生成樹的實用例子,8.4 最小生成樹,二、最小生成樹性質(zhì)MST,設(shè)N=（V，E）是一個連通網(wǎng)， U是頂點(diǎn)集V的一個非空子集。 若（u，v）是一條具有最小權(quán)值的邊，其中uU,v

20、V-U, 即（u，v）=Mincost(x,y)|xU,yV-U 則必存在一棵包含邊（u，v）的最小生成樹。,含義：將頂點(diǎn)分為兩個不相交的集合U和V-U， 若邊（u，v）是連接這兩個頂點(diǎn)集的最小權(quán)值邊，則邊（u，v）必然是某最小生成樹的邊。,三、普里姆（Prim）最小生成樹算法,設(shè) N=（V，E）是一個連通網(wǎng)， V=1，2，n是N的頂點(diǎn)集合， 輔助集合U，初值為Uo， 用來存放當(dāng)前所得到的最小生成樹的頂點(diǎn)； 輔助集合TE，初值為， 用來存放當(dāng)前所得到的最小生成樹的邊。,Prim算法步驟,1. TE=,U=u0 2. 當(dāng)UV，重復(fù)下列步驟： (1)選取（u0,v0)=mincost(u,v)|u

21、U,vV-U，保證不形成回路 (2)TE=TE+（u0,v0), 邊（u0,v0)并入TE (3)U=U+V0，頂點(diǎn)V0 并入U,特點(diǎn): 以連通為主 選代價最小的鄰接邊,Prim算法實現(xiàn): void minispantree_PRIM(mgraph G. vextextype u) / 從u出發(fā)構(gòu)造網(wǎng) gn的最小生成樹 k=locatevex (G,u) ; FOR (j=0;j0) printf(closedgek.adjvex,G.vexk); /輸出生成樹的邊 closedgek.lowcost=0; /頂點(diǎn)k并入U FOR (j=0 ; jG.vexnum ; +j ) IF ( G.

22、arcs kj.adj closedgej.lowcost ) closedgej = G.vexsk,G.arcskj.adj ; /該圖的鄰接矩陣 /新頂點(diǎn)并入U后，重選最小代價邊 ,算法minispantree_PRIM的幾點(diǎn)說明: 1. g為 網(wǎng)的鄰接矩陣 即 gi, j=w ij 或 為無窮大 2. 輔助數(shù)組closedge1.n 有兩個分量: closedgek.vex存放邊(k, j)依附的另一頂點(diǎn)j( jU) closedgek.lowcost存放邊(k, j)的權(quán)值，當(dāng)值為0時，表示頂點(diǎn)k已加入到集合U中。 區(qū)別頂點(diǎn) U或V-U，是根據(jù)， .lowcost=0 U .lowc

23、ost0 V-U closedgek.vex U 而 k V-U,算法minispantree_PRIM的幾點(diǎn)說明: 3. Int minimum(closedge) min:=; h:=1; FOR (k=1 , kG. vtxnum ; +k) IF (closedgek.lowcost ) /minimum,例子：,四、克魯斯卡爾（Kruskal）最小生成樹算法,Kruskal 算法是逐步給生成樹T中添加不和T中的邊構(gòu)成回路的當(dāng)前最小代價邊。 特點(diǎn): 以最小代價邊主。 設(shè)N=（V，E）是個連通網(wǎng), 算法步驟為： 1. 置生成樹T的初始狀態(tài)為T=（V，） 2. 當(dāng)T中邊數(shù)n-1時, 重復(fù)下

24、列步驟: 從E中選取代價最小的邊（v, u）, 并刪除之; 若（v, u）依附的頂點(diǎn)v和u落在T中不同的連同分量上， 則將邊（v, u）并入到T的邊集中； 否則，舍去該邊，選擇下一條代價最小的邊.,四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E T,1 (1, 3),0,1,四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E T,3 (2, 5),2 (4, 6),四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E T,5 (1, 4),4 (3, 6),四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E T,

25、6 (2, 3),邊數(shù)=n-1=5 代價=(1+2+3+4+5)=15,思考： 已知世界大城市：北京（B）,紐約（N），巴黎（P），倫敦（L），東京（T），墨西哥（M）試確定如下表的交通網(wǎng)中的最小生成樹,N,P,B,L,M,T,3,思考： 什么樣的圖其最小生成樹是惟一的？Prim Kruskal 分別適合于哪類圖？,各條邊權(quán)值不相同的有向圖，其最小生成樹是惟一的 Prim適合頂點(diǎn)比較少的圖kruskal 適合邊比較少的圖,思考： 下圖是各個城市間的交通情況圖，如何能造成破壞性,關(guān)節(jié)點(diǎn)和重連通分量,關(guān)節(jié)點(diǎn)： 假若在刪去頂點(diǎn)v 以及和v相關(guān)聯(lián)的各邊之后，將圖的一個連通分量分割成兩個或兩個以上的連通

26、分量，則稱頂點(diǎn)v為該圖的一個關(guān)節(jié)點(diǎn)(articulation point) 。 重連通圖： 一個沒有關(guān)節(jié)點(diǎn)的連通圖稱為重連通圖(biconnected graph),關(guān)節(jié)點(diǎn)ABG,8.5 拓?fù)渑判?topological sort) 拓?fù)渑判蚴且环N對非線性結(jié)構(gòu)的有向圖進(jìn)行線性化的重要手段 一、AOV網(wǎng)(Activity on vertex network) 一個有向圖可用來表示一個施工流程圖、一個產(chǎn)品生產(chǎn)流程圖、或一個程序框圖等。如圖：,課程安排,Pascal,DS,Compiler,OS,C,施工從活動 a1、 a2開始，到達(dá)活動 a8和 a9時，整個施工結(jié)束。 有向圖中，頂點(diǎn)表示活動，弧表

27、示活動 ai優(yōu)先于活動 aj ， 稱這類有向圖為頂點(diǎn)表示活動的網(wǎng)（AOV網(wǎng)）。,8.5 拓?fù)渑判?topological sort),AOV網(wǎng)可解決如下兩個問題： （1）判定工程的可行性。顯然，有回路，整個工程就無法結(jié)束 （2）確定各項活動在整個工程執(zhí)行中的先后順序。 稱這種先后順序為拓?fù)溆行蛐蛄小?如圖有如下拓?fù)溆行蛐蛄校?a1 a2 a3a4 a6 a5 a7 a8 a9 a2 a6 a1 a3 a4 a5 a7 a9 a8,8.5 拓?fù)渑判?topological sort),拓?fù)渑判颍簼M足以下性質(zhì)的線性序列： 在AOV網(wǎng)中，若頂點(diǎn)i 優(yōu)先于頂點(diǎn)j ，則在線性序列中頂點(diǎn)i仍然優(yōu)先于頂點(diǎn)j

28、； 對于網(wǎng)中原來沒有優(yōu)先關(guān)系的頂點(diǎn)與頂點(diǎn) ，在線性序列中也建立一個先后關(guān)系，或者頂點(diǎn)i優(yōu)先于頂點(diǎn)j ，或者頂點(diǎn)j 優(yōu)先于i。,二、拓?fù)渑判蛩惴?1. 算法步驟 (1) 在AOV網(wǎng)中，選取一個沒有前驅(qū)的頂點(diǎn)輸出； (2) 刪除該頂點(diǎn)和所有以它為弧尾的??； (3) 重復(fù)以上兩步，直到 AOV網(wǎng)中全部頂點(diǎn)都已輸出（得到拓?fù)溆行蛐蛄校?或者，圖中再無沒有前驅(qū)的頂點(diǎn)（AOV網(wǎng)中有環(huán)）,二、拓?fù)渑判蛩惴?如何實現(xiàn)算法中的(1)和(2)？ 對于(1)，沒有前驅(qū)的頂點(diǎn)即入度為0的頂點(diǎn)； 對于(2)，刪除以它為弧尾的所有弧，即讓該頂點(diǎn)的所有直接后繼的入度減1。,由此分析知：拓?fù)渑判蛩惴ǖ膶崿F(xiàn)與頂點(diǎn)的入度有密切關(guān)

29、系，因此，在選取存儲結(jié)構(gòu)時，應(yīng)考慮： 能容易得到各頂點(diǎn)的入度； 有利于尋找任一頂點(diǎn)的所有直接后繼。 為此，采用鄰接表作為AOV網(wǎng)的存儲結(jié)構(gòu)，并在頭結(jié)點(diǎn)中增加一個存放頂點(diǎn)入度的域（indegree）,二、拓?fù)渑判蛩惴?Status toposort(algraph G)/G采用鄰接鏈表存儲。若無回路輸出拓?fù)湫蛄?finddegree(G,indegree ); /對各頂點(diǎn)求入度，indegree0.vernum-1 INITstack (s); FOR (i=0 ; Inextarc ) k=p-adjvex ; /下面對I號頂點(diǎn)的每個鄰接點(diǎn)的入度-1 if (!(-indegreek) PUS

30、H(top, k); /入度減為0的頂點(diǎn)入棧 /for /while IF (count G.vexnum) RETURN error ; /有回路 ELSE RETURN ok; / toposort,8.6 關(guān)鍵路徑,一、AOE網(wǎng)（activity on edge） 若有向圖中，頂點(diǎn)表示事件，弧表示活動，弧上的權(quán)表示完成該活動所需的時間，則稱這類有向圖為邊表示活動的網(wǎng)（AOE網(wǎng)） AOE網(wǎng)中僅有一個入度為0的事件，稱為源點(diǎn)，它表示工程的開始；網(wǎng)中也僅有一個出度為0的事件，稱為匯點(diǎn)，它表示工程的結(jié)束。 每一事件V表示以它為弧頭的所有活動已經(jīng)完成，同時，也表示以它為弧尾的所有活動可以開始。,8

31、.6 關(guān)鍵路徑,AOE網(wǎng)可解決如下問題： 估算工程的最短工期（從源點(diǎn)到 匯點(diǎn)至少需要多少時間） 找出哪些活動是影響整個工程進(jìn)展的關(guān)鍵,有4個事件：V1， V2， V3， V5 V1為源點(diǎn)，V5為匯點(diǎn) 有4個活動：a1, a2, a4, a5 V3表示：a2已完成，a5可以開始,8.6 關(guān)鍵路徑,二、幾個術(shù)語 路徑長度：路徑上各活動持續(xù)時間的總和 （即：路徑上所有弧的權(quán)值之和） 關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)之間路徑長度最長的路徑， （不一定唯一） 事件V i的最早發(fā)生時間ve(i)：從源點(diǎn)到V i的最長路徑長度 活動 ai的最早開始時間e(i)：等于該活動的弧尾事件V j的最早發(fā)生時間 即若表示活動a

32、i ，則有e(i)=ve(j),vj,vk,ai,vr,8.6 關(guān)鍵路徑,事件 vk 的最遲發(fā)生時間 vl(k)：是在不推遲整個工期的前提下，該事件最遲必須發(fā)生的時間 活動ai的最遲開始時間l(i)：是該活動的弧頭事件的最遲發(fā)生時間與該活動的持續(xù)時間之差， 即l(i)=vl(k)- ai 的持續(xù)時間 關(guān)鍵活動：l(i)=e(i)的活動,由此可見：在AOE網(wǎng)中找關(guān)鍵活動問題可轉(zhuǎn)化為求 l(i)=e(i)，而e(i)=ve(j) l(i)=vl(k) - ai 的持續(xù)時間 因此，需先求出事件的最早、最遲發(fā)生時間,v2,v3,v1,v4,v5,2,2,4,5,6,3,8.6 關(guān)鍵路徑,三、關(guān)鍵路徑算

33、法思想 1. 從ve(1)=0 開始利用下面遞推公式，計算出各事件的最早發(fā)生時間 ve(j)=Maxve(i)+dut()， j=2, n， T 其中：T是所有以j為頭的弧集合， dut()表示活動的持續(xù)時間 前例中，ve(5)=Maxve(2)+dut()， ve(3)+dut() =Max6+1,4+1=7,2. 從vl(n)=ve(n)開始，利用下面遞推公式，計算出各時間的最遲發(fā)生時間： vl(i)=Minvl(j)-dut() i=n-1 , 2, 1 , S 其中：S是所有以i為尾的弧集合,8.6 關(guān)鍵路徑,前例中，vl(5)=ve(5)=7 vl(2)=vl(5)-1=6 vl(3

34、)=vl(5)-1=6 vl(1)=Minvl(2)-dut()，vl(3)-dut() =Min6-6,6-4=0,8.6 關(guān)鍵路徑,3. 設(shè)活動ai由弧表示，其持續(xù)時間為dut()，則利用下面公式，計算出各活動的最早、最遲開始時間： e(i)=ve(j) l(i)=vl(k)-dut() 4. 找出e(i)=l(i)的活動，即為關(guān)鍵活動，諸關(guān)鍵活動組成的從源點(diǎn)到匯點(diǎn)的路徑即為關(guān)鍵路徑。,Ve1=0 Vek=maxvej+,Vln=ven Vlk=minvlj-,ei=vek li=vlj-,ve (1)=0 ve (2)=3 ve (3)=4 ve (4)=ve(2)+2=5 ve (5)

35、=maxve(2)+1,ve(3)+3=7 ve (6)=ve(3)+5=9 ve (7)=maxve(4)+6,ve(5)+8=15 ve (8)=ve(5)+4=11 ve (9)=maxve(8)+10,ve(6)+2=21 ve (10)=maxve(8)+4,ve(9)+1=22 ve (11)=maxve(7)+7,ve(10)+6=28,vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21 vl (8)=min vl (10)-4, vl (9)-10=11 vl (7)= vl (11)-7=21 vl (

36、6)= vl (9)-2=19 vl (5)=min vl (7)-8,vl (8)-4=7 vl (4)= vl (7)-6=15 vl (3)=min vl (5)-3, vl (6)-5=4 vl (2)=min vl (4)-2, vl (5)-1=6 vl (1)=minvl (2)-3, vl (3)-4=0,活動a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活動a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活動a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活動a4 e (4)=ve (2)=3

37、l (4)=vl (5) - 1=6 活動a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活動a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活動a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活動a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活動a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活動a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活動a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活動a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活動