數(shù)據(jù)結構課件07

1、第七章第七章 圖圖精英專升本精英專升本V1V2V3V4G1V1V2V4V5G2V3ABECFAEFBBC1597211132C V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2例例:(b)、(c) 是是 (a) 的子圖的子圖(a) (b) (c) ACDFE例如例如: :ID(B) = 3ID(A) = 2BABECF對有向圖來說對有向圖來說，例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3ABECF 非連通圖非連通圖 連通圖連通圖 強連通圖強連通圖 非強連通圖非強連通圖 V

2、0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4在無（在無（有有）向圖）向圖G=( V, E )G=( V, E )中，若對任何兩個頂點中，若對任何兩個頂點 v v、u u 都存在從都存在從v v 到到 u u 的路徑，則稱的路徑，則稱G G是連通圖（是連通圖（強連通圖強連通圖）。）。非連通圖非連通圖 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4無向圖無向圖G G 的的稱為稱為G G的連通分量。的連通分量。極大連通子圖意思是：該子圖是極大連通子

3、圖意思是：該子圖是 G G 連通子圖，將連通子圖，將G G 的任何不在該子圖中的頂點加入，子圖不再連通。的任何不在該子圖中的頂點加入，子圖不再連通。 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4連通分量連通分量有向圖有向圖G G 的的稱為稱為G G的強連通分量。極的強連通分量。極大強連通子圖意思是：該子圖是大強連通子圖意思是：該子圖是G G的強連通子圖，將的強連通子圖，將D D的任何不在該子圖中的頂點加入，子圖不再是強連的任何不在該子圖中的頂點加入，子圖不再是強連通的。通的。強連通分量強連通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1：該子

4、圖是：該子圖是G G 的連通子圖，在該子圖的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。中刪除任何一條邊，子圖不再連通。包含無向連通圖包含無向連通圖G G 所有頂點的極小連通子所有頂點的極小連通子圖。圖。對非連通圖，由各個連通分量的生對非連通圖，由各個連通分量的生成樹的集合。成樹的集合。 連通圖連通圖 G1G1G1G1的生成樹的生成樹 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V27.2 7.2 圖的存儲結構圖的存儲結構數(shù)組表示法（鄰接矩陣）數(shù)組表示法（鄰接矩陣）多重鏈表多重鏈表0 (i

5、,j)VR1 (i,j)VR一、一、圖的數(shù)組(鄰接矩陣)存儲表示BACDFE定義定義:矩陣的元素為矩陣的元素為A B C D E FABCDEF有向圖的鄰接矩陣有向圖的鄰接矩陣為非對稱矩陣為非對稱矩陣ABECF0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0typedef struct ArcCell / 弧的定義弧的定義 VRType adj; / VRType是頂點關系類型。 / 對無權圖，用1或0表示相鄰否； / 對帶權圖，則為權值類型。 InfoType *info; / 該弧相關信息的指針 ArcCell, typedef struct /

6、圖的定義圖的定義 VertexType / 頂點信息 / 弧的信息 int vexnum, arcnum; / 頂點數(shù)，弧數(shù) GraphKind kind; / 圖的種類標志 MGraph; , ),( , , .AMGraph 否否則則或或者者如如果果01A ; EjiEjijiarcs鄰接矩陣：G1.arcs =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點表：無向圖的鄰接矩陣表示法無向圖的鄰接矩陣表示法v1v2v3v5v4v4有向圖的鄰接矩陣有向圖的鄰接矩陣可能是不對稱可能是不對稱的。

7、的。頂點的頂點的出度出度= =第第i i行元素之和行元素之和 頂點的頂點的入度入度= =第第i i列元素之和列元素之和 頂點的頂點的度度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和 v1v2v3v4鄰接矩陣：( v1 v2 v3 v4 )v1v2v3v4注：注：在有向圖的鄰接矩陣中，在有向圖的鄰接矩陣中， 第第i i行含義：以結點行含義：以結點v vi i為尾的弧為尾的弧( (即出度邊）；即出度邊）； 第第i i列含義：以結點列含義：以結點v vi i為頭的弧為頭的弧( (即入度邊）。即入度邊）。頂點表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0

8、有向圖的鄰接矩陣表示法有向圖的鄰接矩陣表示法定義為：定義為： N.arcs i j =Wij 或（或（vi, vj）VR 無邊（?。o邊（弧）N5489755613鄰接矩陣：N.arcs =( v1 v2 v3 v4 v5 v6 )頂點表： 5 7 4 8 9 5 6 5 3 1 網（即有權圖）的鄰接矩陣表示法網（即有權圖）的鄰接矩陣表示法優(yōu)點：優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊、找頂點的鄰接點等等。點之間是否有邊、找頂點的鄰接點等等。缺點：缺點：n n個頂點需要個頂點需要n n* *n n個單元存儲邊個單元存儲邊; ;空間

9、效率為空間效率為O(nO(n2 2) )。 對稀疏圖而言尤其浪費空間。對稀疏圖而言尤其浪費空間。鄰接矩陣表示法的特點鄰接矩陣表示法的特點0 A1 B2 C3 D4 E5 FBACDFE二、圖的鄰接表二、圖的鄰接表 存儲表示存儲表示1 40 4 53 52 50 11 2 3v 以每個頂點以每個頂點vi 作為頭結點，建立一個作為頭結點，建立一個，把與，把與vi有關聯(lián)的有關聯(lián)的起來起來設兩個域，表中每個設兩個域，表中每個設為設為3個域；個域；鄰接點域鄰接點域，表表示示vi一個鄰接一個鄰接點的位置點的位置鏈域鏈域，指向指向vi下一個邊下一個邊或弧的結點或弧的結點數(shù)據(jù)域數(shù)據(jù)域，與與邊有關信息邊有關信息

10、（如權值）（如權值）數(shù)據(jù)域數(shù)據(jù)域，存存儲頂點儲頂點vi 信信息息鏈域鏈域，指向，指向單鏈表的第單鏈表的第一個結點一個結點adjvexnextarcinfodatafirstarc鄰接表（鏈式）表示法鄰接表（鏈式）表示法0123413341420注：注：鄰接表不唯一鄰接表不唯一，因各個邊結點的鏈入順序是任意的，因各個邊結點的鏈入順序是任意的v1v2v3v4v5231420無向圖的鄰接表表示無向圖的鄰接表表示TD(ViTD(Vi)=)=單鏈表中鏈接的結點個數(shù)單鏈表中鏈接的結點個數(shù)v1v2v3v5v4v4有向圖的鄰接表有向圖的鄰接表1 4230 120 1 2 3 4 A B C D EABECD可

11、見，在有向圖的鄰接表中不易找到指向該頂點的弧。出度出度入度入度度：度：OD(ViOD(Vi) )單鏈出邊表中鏈接的結點數(shù)單鏈出邊表中鏈接的結點數(shù)ID(ViID(Vi) )鄰接點域為鄰接點域為ViVi的弧個數(shù)的弧個數(shù)TD(Vi) = OD( Vi ) + I D( Vi )ABECD有向圖的逆鄰接表有向圖的逆鄰接表A B C D E 303420 01234在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。8064125當鄰接表的存當鄰接表的存儲結構形成后，儲結構形成后，圖便唯一確定！圖便唯一確定！已知某網的鄰接（出邊）表，請畫出該網絡。已知某網的鄰接（出邊）表，請畫出該網絡。typed

12、ef struct ArcNode int adjvex; / 該弧所指向的頂點的位置 struct ArcNode *nextarc; / 指向下一條弧的指針 InfoType *info; / 該弧相關信息的指針 ArcNode;adjvex nextarc info弧的結點結構弧的結點結構typedef struct VNode VertexType data; / 頂點信息 ArcNode *firstarc; / 指向第一條依附該頂點的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc頂點頂點的頭結點的頭結點結構結構typedef struct

13、 AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標志 ALGraph;圖的結構定義圖的結構定義v1v2v3v5v4v44321013341420v5v4v3v2v1231420（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0鄰接矩陣與鄰接表表示法的關系鄰接矩陣

14、與鄰接表表示法的關系1. 1. 聯(lián)系：聯(lián)系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數(shù)等于一行中非零元素的個數(shù)。鏈表中結點個數(shù)等于一行中非零元素的個數(shù)。2. 2. 區(qū)別：區(qū)別： 對于任一確定的無向圖，鄰接矩陣是對于任一確定的無向圖，鄰接矩陣是唯一唯一的（行列的（行列號與頂點編號一致），但鄰接表號與頂點編號一致），但鄰接表不唯一不唯一（鏈接次序（鏈接次序與頂點編號無關）。與頂點編號無關）。 鄰接矩陣的空間復雜度為鄰接矩陣的空間復雜度為O(nO(n2 2),),而鄰接表的空間復而鄰接表的空間復雜度為雜度為O(n+eO(n+e) )。3. 3. 用

15、途：用途：鄰接矩陣多用于鄰接矩陣多用于稠密圖稠密圖；而鄰接表多用于；而鄰接表多用于稀稀疏圖疏圖鄰接矩陣與鄰接表表示法的關系鄰接矩陣與鄰接表表示法的關系7.3 圖的遍歷圖的遍歷 從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的的過程。深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索遍歷應用舉例遍歷應用舉例 從圖中某個頂點V0 出發(fā)，訪問此頂點，然后，直至圖中所有和V0有路徑相通的頂點都被訪問到。一、深度優(yōu)先搜索一、深度優(yōu)先搜索遍歷圖（遍歷圖（DFS）連通圖的深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先搜索遍歷Vw1SG1SG2SG3W1、W2和W3 均為 V 的鄰接點，SG1、SG2 和 SG3 分

16、別為含頂點W1、W2和W3 的子圖。w2w3w2基本思想：基本思想：仿樹的先序遍歷過程。仿樹的先序遍歷過程。v1v2v3v8v7v6v4v5起點起點深度優(yōu)先搜索深度優(yōu)先搜索( DFS Depth_First Search)解決思路：解決思路：設置設置輔助數(shù)組輔助數(shù)組 visitedvisited n n ，用來標記每，用來標記每個被訪問過的頂點。個被訪問過的頂點。初始狀態(tài)為初始狀態(tài)為0 0i i 被訪問，改被訪問，改 visitedvisited i i 為為1 1，防止被多次訪問，防止被多次訪問怎樣避免重復訪問？怎樣避免重復訪問？void DFS(Graph G, int v) / 從頂點從

17、頂點v出發(fā)，出發(fā)，深度優(yōu)先搜索遍歷連通圖深度優(yōu)先搜索遍歷連通圖 G /算法調用前，設每個結點的算法調用前，設每個結點的visitedv=FALSE visitedv = TRUE; VisitFunc(v); for( ; ; ) if (!visitedw) DFS(G, w); / 對v的尚未訪問的鄰接頂點w / 遞歸調用DFS / DFS連通圖連通圖的深度優(yōu)先搜索的深度優(yōu)先搜索遍歷算法（遍歷算法（P169算法算法7.5） 首先將圖中每個頂點的訪問標志設為 FALSE, 之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。非連通圖的深度優(yōu)先搜

18、索遍歷非連通圖的深度優(yōu)先搜索遍歷void DFSTraverse(Graph G, Status (*Visit)(int v) / 對圖對圖 G 作深度優(yōu)先遍歷。作深度優(yōu)先遍歷。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標志數(shù)組初始化 for (v=0; vw1, V-w2, V-w8 的路徑長度為1；V-w7, V-w3, V-w5 的路徑長度為2；V-w6, V-w4 的路徑長度為3。w1Vw2w7w6w3w8w5w4基本思想：基本思想：仿樹的層次遍歷過程仿樹的層次遍歷過程廣度優(yōu)先搜索廣度優(yōu)先搜索

19、( BFS Breadth_First Search)v1v2v3v8v7v6v4v5起點起點簡單歸納：簡單歸納：在訪問了在訪問了起始點起始點v之后，依次訪問之后，依次訪問 v的鄰接點的鄰接點；之后按這些頂點被訪問的先后次序，依次訪問它們按這些頂點被訪問的先后次序，依次訪問它們的的未被訪問過的鄰接點未被訪問過的鄰接點；直到所有頂點都被訪問直到所有頂點都被訪問過為止。過為止。廣度優(yōu)先搜索的步驟廣度優(yōu)先搜索的步驟v1v2v3v8v7v6v4v5起點起點V9 void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +

20、v) visitedv = FALSE; /初始化訪問標志 InitQueue(Q); / 置空的輔助隊列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未訪問 / BFSTraverse visitedv = TRUE; Visit(v); / 訪問uEnQueue(Q, v); / v入隊列while (!QueueEmpty(Q) DeQueue(Q, u); / 隊頭元素出隊并置為u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw

21、=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點w入隊列 / if / while真題：已知一有向圖的鄰接表存儲結構如下圖所示，分別根據(jù)圖的深度和廣度優(yōu)先搜索遍歷算法，從頂點v1出發(fā)，得到的頂點序列分別為（ ）和（ ）。A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v2最小生成樹最小生成樹最短路徑最短路徑拓撲排序拓撲排序關鍵路徑關鍵路徑圖的應用（圖的應用（ 7.4 ，7.5，7.6）：該子圖是該子圖是G 的連通子圖，在該子圖中刪除的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。

22、任何一條邊，子圖不再連通。包含圖包含圖G所有頂點的極小連通子圖（所有頂點的極小連通子圖（n-1條邊）條邊）G1G1的生成樹的生成樹連通圖連通圖 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小生成樹最小生成樹DFSDFS生生成成樹樹鄰鄰接接表表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFSBFS生生成成樹樹v0v1v3v2v4無向連通圖無向連通圖畫出下圖的生成樹畫出下圖的生成樹v0v1v2v4v4v3求最小生成樹求最小生成樹首先明確首先明確：

23、使用不同的遍歷圖的方法，可以得到不同的生成樹使用不同的遍歷圖的方法，可以得到不同的生成樹 從不同的頂點出發(fā)，也可能得到不同的生成樹。從不同的頂點出發(fā)，也可能得到不同的生成樹。 按照生成樹的定義，按照生成樹的定義，n n 個頂點的個頂點的連通網絡連通網絡的生成樹的生成樹有有 n n 個頂點、個頂點、n-n-1 1 條邊。條邊。目標：目標：在在的多個生成樹中，尋找一個的多個生成樹中，尋找一個v必須考慮到該必須考慮到該網中的邊的權網中的邊的權來構造最小生成樹；來構造最小生成樹；v必須使用且僅使用必須使用且僅使用n-1n-1條邊條邊來聯(lián)結網絡中的來聯(lián)結網絡中的n n個個頂點頂點v不能使用產生不能使用產

24、生回路回路的邊的邊構造最小生成樹的準則構造最小生成樹的準則最小生成樹即：在 e 條帶權的邊中選取 n-1 條邊（不構成回路），使“權值之和權值之和”為最小。欲在欲在n n個城市間建立通信網，則個城市間建立通信網，則n n個城市應鋪個城市應鋪n-1n-1條條線路；但因為每條線路都會有對應的經濟成本，而線路；但因為每條線路都會有對應的經濟成本，而n n個個城市可能有城市可能有n(n-1)/2 n(n-1)/2 條線路，那么，條線路，那么，如何選擇如何選擇n n1 1條條線路，使總費用最少？線路，使總費用最少？數(shù)學模型：數(shù)學模型：頂點頂點表示城市，有表示城市，有n n個；個；邊邊表示線路，有表示線路

25、，有n n1 1條；條；邊的權值邊的權值表示線路的經濟代價；表示線路的經濟代價；連通網連通網表示表示n n個城市間通信網。個城市間通信網。顯然此連通網顯然此連通網是一個是一個生成樹生成樹！最小生成樹的典型用途最小生成樹的典型用途v PrimPrim（普里姆）算法（普里姆）算法 v KruskalKruskal（克魯斯卡爾）算法（克魯斯卡爾）算法PrimePrime算法算法: : 歸并頂點歸并頂點，與邊數(shù)無關，適于，與邊數(shù)無關，適于稠密網稠密網Kruskal算法：算法：歸并邊歸并邊，適于，適于稀疏網稀疏網如何求最小生成樹如何求最小生成樹 設連通網絡設連通網絡 N = V, E 生成樹的頂點集生成

26、樹的頂點集合合UU普里姆算法的基本思想歸并頂點普里姆算法的基本思想歸并頂點應用普里姆算法構造最小生成樹的過程應用普里姆算法構造最小生成樹的過程 在生成樹的構造過程中，圖中 n 個頂點分屬兩個集合：已落在生成樹上的頂點集 U 和尚未落在生成樹上的頂點集V-U ，則應在所有連通在所有連通U中頂點和中頂點和V-U中中頂點的邊中選取權值最小的邊頂點的邊中選取權值最小的邊。 一般情況下所添加的頂點應滿足下列條件: 設置一個輔助數(shù)組，對當前設置一個輔助數(shù)組，對當前集集中的每個頂點，記錄和頂點集中的每個頂點，記錄和頂點集U中頂點中頂點相連接的相連接的：struct VertexType adjvex; /

27、U集中的頂點序號 VRType lowcost; / 邊的權值 MAX_VERTEX_NUM;abcdegf195141827168213ae12dcb7closedge0123456AdjvexLowcostaaa19141814例如例如:e12ee8168d3dd7213c5 5a b c d e f g16g21fvoid MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法從頂點u出發(fā)構造網G的最小生成樹 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k)

28、closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; +i) 繼續(xù)向生成樹上添加頂點繼續(xù)向生成樹上添加頂點; k = minimum(closedge); / 求出加入生成樹的下一個頂點(k) printf(closedgek.adjvex, G.vexsk); / 輸出生成樹上一條邊 closedgek.lowcost = 0; / 第k頂點并入U集 for (j=0; jG.vexnum; +j) /修改其它頂點的最小邊 if (G.arcskj.adj closedgej.low

29、cost) closedgej = G.vexsk, G.arcskj.adj ; 設連通網絡設連通網絡 N = V, E 1. 構造一個只有構造一個只有 n 個頂點，沒有邊的非連通圖個頂點，沒有邊的非連通圖 T = V, , 每個頂點自成一個連通分量每個頂點自成一個連通分量 2. 在在 E 中選最小權值的邊中選最小權值的邊,若該邊的兩個頂點落在若該邊的兩個頂點落在不同的連通分量上，則加入不同的連通分量上，則加入 T 中；否則舍去，重中；否則舍去，重新選擇新選擇 3. 重復下去，直到所有頂點在同一連通分量上為重復下去，直到所有頂點在同一連通分量上為止止克魯斯卡爾算法的基本思想歸并邊克魯斯卡爾算

30、法的基本思想歸并邊應用克魯斯卡爾算法構造最小生成樹的過程應用克魯斯卡爾算法構造最小生成樹的過程普里姆算法普里姆算法 克魯斯卡爾算法克魯斯卡爾算法時間復雜度時間復雜度O(n2)O(eloge)稠密圖稠密圖稀疏圖稀疏圖算法名算法名適應范圍適應范圍比較兩種算法如果用有向圖來描述一個工程或系統(tǒng)的進行過程，則圖中不允許出現(xiàn)回路。有向無環(huán)圖簡稱圖。比如教學計劃的制定比如教學計劃的制定哪些課程是必須先修的，哪些課程是可以并行學習的。哪些課程是必須先修的，哪些課程是可以并行學習的。7.5 有向無環(huán)圖及其應用有向無環(huán)圖及其應用如：用有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖學生課程學習工程圖學生課程學習工程圖對

31、有向圖進行如下操作： 按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系。由此所得頂點的線性序列稱之為7.5.1 拓撲排序拓撲排序例如：對于下列有向圖BDAC可求得拓撲有序序列： A B C D 或 A C B DBDAC反之，對于下列有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路 B, C, D1.輸入輸入AOV網絡。令網絡。令 n 為頂點個數(shù)。為頂點個數(shù)。2. 在在AOV網絡中網絡中選一個沒有直接前驅的頂點選一個沒有直接前驅的頂點, 并輸出之并輸出之; 3. 從圖中刪去該頂點從圖中刪去該頂點, 同時刪去所有它發(fā)出的有

32、向邊同時刪去所有它發(fā)出的有向邊;4. 重復以上重復以上 2、3 步步, 直到：直到：u全部頂點均已輸出，拓撲有序序列形成，拓撲排序全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或：完成；或：u圖中還有未輸出的頂點，但已跳出處理循環(huán)。圖中還有未輸出的頂點，但已跳出處理循環(huán)。，再也，再也找不到沒有前驅的頂點了。這時找不到沒有前驅的頂點了。這時。拓撲排序的過程拓撲排序的過程a3=6a5=47.5.2 關鍵路徑關鍵路徑AOE網用邊表示活動，頂點表示事件，弧上的權值表示完成該項活動所需時間整個工程只有一個開始點和一個結束點。源點匯點abcdefghk64521187244例如例如: :整個工程完成的

33、時間為：從有向圖的源點源點到匯點匯點的最長路徑。6174a1a2a3a4a5a6a7a8a9a10a11 假設第 i 條活動ai（?。?， 定義“活動ai (弧)”的 最早開工時間 定義“活動ai (弧)”的 最遲開始時間 abcdefghk64521187244a1a2a3a4a5a6a7a8a9a10a11整個活動的完成時間整個活動的完成時間18“事件事件(頂點頂點)” 的 最早發(fā)生時間 設活動設活動ai用弧用弧表示，其持續(xù)時間記為：表示，其持續(xù)時間記為：dut()則有：則有：（1）ee(i)=Ve(j)（2）el(i)=Vl(k)-dut()jkai987645321a2=4a3=5a

34、5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4(1)從從Ve(1)=0開始向前遞推開始向前遞推為頭的弧的集合是所有以其中2,),()()(jTnjTjijidutiVeMaxjVeiabcdefghk64521187244a1a2a3a4a5a6a7a8a9a10a11Ve(b)=6; Ve(c)=4; Ve(e)=7; (2)從從Vl(n)=Ve(n)開始向后遞推開始向后遞推為尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(abcdefghk64521187244a1a2a3a4a5a6a7a8a9a10a11Vl(g)=

35、16; Vl(h)=14; Vl(e)=7;Vl(b)=6整個活動的完成時間整個活動的完成時間18Vl(k)=Ve(k)=18abcdefghk64521187244a b c d efg h kvevl0000000006457115 715 14 1818181818181818181816 1486610807（1）列出所有的）列出所有的關鍵路徑關鍵路徑；（2）完成整個工程）完成整個工程至少至少需要多少時間？需要多少時間？（3）事件）事件V5 的最早的最早完成完成時間是多少？時間是多少？（4）活動）活動 a6 的的最早最早開工時間是多少？開工時間是多少？練習：對于下面的練習：對于下面的A

36、OEAOE網絡，試回答下列問題：網絡，試回答下列問題：典型用途：典型用途：交通問題。如：城市交通問題。如：城市A A到城市到城市B B有多條線路，有多條線路，但每條線路的交通費（或所需時間）不同，那么，但每條線路的交通費（或所需時間）不同，那么，如如何選擇一條線路，使總費用（或總時間）最少？何選擇一條線路，使總費用（或總時間）最少？問題抽象：問題抽象：在在帶權有向圖帶權有向圖中中A A點（源點）到達點（源點）到達B B點（終點（終點）的多條路徑中，尋找一條點）的多條路徑中，尋找一條各邊權值之和最小各邊權值之和最小的路的路徑，即最短路徑。徑，即最短路徑。（注：最短路徑與最小生成樹不同，路徑上（注

37、：最短路徑與最小生成樹不同，路徑上不一定包含不一定包含n n個頂點）個頂點）7.6 7.6 最短路徑最短路徑一頂點到一頂點到其余各頂其余各頂點點兩種常見的最短路徑問題：兩種常見的最短路徑問題：一、一、 單源最短路徑單源最短路徑用用Dijkstra（迪杰斯特拉）（迪杰斯特拉）算法算法二、所有頂點間的最短路徑二、所有頂點間的最短路徑用用Floyd（弗洛伊德）（弗洛伊德）算法算法任意兩頂任意兩頂點之間點之間目的：目的： 設一設一有向圖有向圖G=G=（V, EV, E），已知各邊的權值，以某指定），已知各邊的權值，以某指定點點v v0 0為源點，求從為源點，求從v v0 0到圖的其余各點的最短路徑。到

38、圖的其余各點的最短路徑。限定各邊上限定各邊上的權值大于或等于的權值大于或等于0 0。源點源點從從FAFA的路徑有的路徑有4 4條：條： FAFA： 2424 FBA FBA： 5 518=2318=23 FBCA FBCA：5+7+9=215+7+9=21 FDCAFDCA：25+12+9=3625+12+9=36又：又：從從FBFB的最短路徑是哪條？的最短路徑是哪條？從從FCFC的最短路徑是哪條？的最短路徑是哪條？單源最短路徑問題（單源最短路徑問題（Dijkstra算法）算法） 依依路徑路徑的長度的長度遞增的次序求得遞增的次序求得各節(jié)點的最短路徑各節(jié)點的最短路徑V0v1v2V34263213基本思想（基本思想（Dijkstra算法）算法）V0v1v2V34263213基本思想（基本思想（Dijkstra算法）算法） 依依路徑路徑的長度的長度遞增的次序求得遞增的次序求得各節(jié)點的最短路徑各節(jié)