1、1 7.1 基本術語基本術語 7.2 存儲結構存儲結構 7.3 圖的遍歷圖的遍歷 7.4 圖的連通性問題圖的連通性問題 7.5 有向無環圖及其應用有向無環圖及其應用 7.6 最短路徑最短路徑第7章 圖2圖圖：記為：記為 G( V, E ) 其中：其中：V 是是G的的頂點頂點集合，是有窮非空集；集合，是有窮非空集； E 是是G的的邊邊集合，是有窮集。集合，是有窮集。問：當問：當E(G)E(G)為空時，圖為空時，圖G G存在否？存在否？答：還存在！但此時圖答：還存在！但此時圖G G只有頂點而沒有邊。只有頂點而沒有邊。V=vertex E=edgeabcev4 dG2=(V2,E2), 其中其中V2

2、=a,b,c,d,e,E2=(a,b),(a,d),(b,c),(b,e),(c,e) ,(c,d) ,(d,e)abcdG1=(V1,E1)，其中，其中V1=a,b,c,d, E1=,7.1 圖的基本術語圖的基本術語3證明：有向圖：有向圖：無向圖：無向圖：圖圖G G中的每條邊都是有方向的；中的每條邊都是有方向的；圖圖G G中的每條邊都是無方向的；中的每條邊都是無方向的；7.1 圖的基本術語圖的基本術語4無向無向無向圖無向圖(樹樹)有向圖有向圖有向有向完全圖完全圖完全圖完全圖例：例：判斷下列判斷下列4種圖形各屬什么類型？種圖形各屬什么類型？7.1 圖的基本術語圖的基本術語5設有兩個圖設有兩個圖

3、 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 則則稱稱 圖圖G 是是 圖圖G 的子圖。的子圖。子 圖：邊較少的圖。通常邊數邊較少的圖。通常邊數n2邊很多的圖。無向圖中，邊數接近邊很多的圖。無向圖中，邊數接近有向圖中，邊數接近有向圖中，邊數接近稀疏圖：稠密圖：7.1 圖的基本術語圖的基本術語6即即邊上帶權邊上帶權的圖。其中的圖。其中權權是指每條邊可以標上具有某種含義的是指每條邊可以標上具有某種含義的數值（即與邊相關的數）。數值（即與邊相關的數）。網網 絡：絡：有向邊有向邊稱為弧，邊的始點稱為弧，邊的始點u叫弧尾，終點叫弧尾，終點v叫弧頭叫弧頭 頂點頂點v的度是與它相關聯

4、的邊的條數。記作的度是與它相關聯的邊的條數。記作TD(v)。 在有向圖中在有向圖中, 頂點的度等于該頂點的入度與出度之和。頂點的度等于該頂點的入度與出度之和。 頂點頂點 v 的入度是以的入度是以 v 為頭的弧的數目為頭的弧的數目, 記作記作 ID(v); 頂點頂點 v 的出度是以的出度是以 v 為尾的弧的數目為尾的弧的數目,記作記作 OD(v)。若若 (u, v) 是是 E(G) 中的一條邊，則稱中的一條邊，則稱 u 與與 v 互為鄰接點。互為鄰接點。頂點和邊頂點和邊(u, v)相關聯。相關聯。弧頭和弧尾：度、入度和出度：鄰接點：abcev4 dabcd7.1 圖的基本術語圖的基本術語7路徑上

5、各頂點路徑上各頂點 v v1 1,v,v2 2,.,v,.,vm m 均不互相重復。均不互相重復。回 路：例：例：若路徑上第一個頂點若路徑上第一個頂點 v v1 1 與最后一個頂點與最后一個頂點v vm m 重合，則稱這樣重合，則稱這樣的路徑為回路或環。的路徑為回路或環。路 徑：在圖在圖 G(V, E) 中中, 若從頂點若從頂點 vi 出發出發, 沿一些邊經過一些頂點沿一些邊經過一些頂點 vp1, vp2, , vpm，到達頂點，到達頂點vj。則稱頂點序列。則稱頂點序列 ( vi vp1 vp2 . vpm vj ) 為從頂點為從頂點vi 到頂點到頂點 vj 的路徑。它經過的邊的路徑。它經過的

6、邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj)應當是屬于應當是屬于E的邊。的邊。路徑長度：非帶權圖的路徑長度是指此路徑上邊的條數；非帶權圖的路徑長度是指此路徑上邊的條數；帶權圖帶權圖(網絡網絡)的路徑長度是指路徑上各邊的權之和。的路徑長度是指路徑上各邊的權之和。簡單路徑：有兩類圖形不在本章討論之列：有兩類圖形不在本章討論之列：abcev4 d7.1 圖的基本術語圖的基本術語8連通圖：連通圖：在在無向無向圖中圖中, 若從頂點若從頂點v1到頂點到頂點v2有路徑有路徑, 則稱頂點則稱頂點v1與與v2是連通是連通的。如果圖中任意一對頂點都是連通的的。如果圖中任意一對頂點都是連通的,

7、 則稱此圖是連通圖。則稱此圖是連通圖。非連通圖的極大連通子圖叫做非連通圖的極大連通子圖叫做連通分量連通分量。在在有向圖有向圖中中, 若對于每一對頂點若對于每一對頂點vi和和vj, 都存在一條從都存在一條從vi到到vj和從和從vj到到vi的路徑的路徑, 則稱此圖是強連通圖。則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做非強連通圖的極大強連通子圖叫做強連通分量強連通分量。強連通圖：強連通圖：ABCDABCDEABCDABCDEF7.1 圖的基本術語圖的基本術語9生成樹：生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有是一個極小連通子圖，它含有圖中全部頂點，但只有n-1條邊。條邊。v如果在

8、生成樹上添加如果在生成樹上添加1條邊，必定構成一個環。條邊，必定構成一個環。v若圖中有若圖中有n個頂點，卻少于個頂點，卻少于n-1條邊，必為非連通圖。條邊，必為非連通圖。若干棵生成樹的集合，含全部頂點，但構成這些樹的邊或弧若干棵生成樹的集合，含全部頂點，但構成這些樹的邊或弧是最少的。是最少的。生成森林：生成森林：7.1 圖的基本術語圖的基本術語10圖的特點：非線性結構（圖的特點：非線性結構（m :n m :n ） 鄰接表鄰接表 鄰接多重表鄰接多重表 十字鏈表十字鏈表設計為鄰接矩設計為鄰接矩陣陣鏈式存儲結構：鏈式存儲結構：順序存儲結構：順序存儲結構： 無！無！（多個頂點，無序可言）（多個頂點，無

9、序可言）但可但可用用描述元素間關系。描述元素間關系。可用多重鏈表可用多重鏈表重點介紹：重點介紹：7.2 圖的存儲結構圖的存儲結構11v 建立一個建立一個頂點表頂點表（記錄各個頂點信息）（記錄各個頂點信息）和一個和一個鄰接矩陣鄰接矩陣（表示各個（表示各個頂點之間關系）頂點之間關系）。v 設圖設圖 A = (V, E) 有有 n 個頂點，則圖的鄰接矩陣是一個二維數組個頂點，則圖的鄰接矩陣是一個二維數組 A.Edgenn，定義為：，定義為：一、鄰接矩陣（數組）表示法一、鄰接矩陣（數組）表示法A.Edgeij=1，如果E或者(i,j) E0，否則7.2 圖的存儲結構圖的存儲結構12v1v2v3v5v4

10、v4A例1：無向圖的鄰接矩陣鄰接矩陣：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v5分析分析1：無向圖的鄰接矩陣是無向圖的鄰接矩陣是對稱對稱的；的；分析分析2：頂點頂點i 的度的度第第 i 行行 (列列) 中中1 的個數的個數；特特 別：別：無向無向完全圖完全圖的鄰接矩陣中，對角元素為的鄰接矩陣中，對角元素為0，其余全，其余全1。頂點表：0 10 101 01 010 10 111 01 010 11 107.2 圖的存儲結構圖的存儲結構13有向圖的鄰接矩陣有向圖的鄰接矩陣可能是不對稱可能是不對稱的。的。頂點的頂點的出度出度= =第第i i行元素之和，行元素之和， 頂

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

12、儲結構14 容易實現圖的操作，如：求某頂點的度、判斷容易實現圖的操作，如：求某頂點的度、判斷 頂點之間是否有邊（弧）、找頂點的鄰接點等等。頂點之間是否有邊（弧）、找頂點的鄰接點等等。 n n個頂點需要個頂點需要n n* *n n個單元存儲邊個單元存儲邊( (弧弧); ); 對稀疏圖而對稀疏圖而 言尤其浪費空間。言尤其浪費空間。定義為：定義為：v1v2v3v4Nv5v65489755613鄰接矩陣：N.Edge =( v1 v2 v3 v4 v5 v6 )鄰接矩陣法鄰接矩陣法優點：優點：鄰接矩陣法鄰接矩陣法缺點：缺點：頂點表：例例3 3：網（即有權圖）的鄰接矩陣A.Edgeij=Wij，如果E或

13、者(i,j) E，無邊（無弧） 5 7 4 8 9 5 6 5 3 1 7.2 圖的存儲結構圖的存儲結構15v 每個單鏈表還應當附設一個頭結點（設為每個單鏈表還應當附設一個頭結點（設為2個域），存個域），存vi信息；信息；adjvexnextarcinfodatafirstarc鄰接點域，鄰接點域，表表示與示與v vi i鄰接的點鄰接的點在圖中位置在圖中位置鏈域，鏈域，指向指向vivi下一個邊下一個邊或弧的結點或弧的結點數據域，數據域，與邊有關與邊有關信息（如信息（如權值）權值）數據域，存數據域，存儲頂點儲頂點vi 信信息息鏈域，鏈域，指向指向單鏈表的第單鏈表的第一個結點一個結點v 每個單鏈表

14、的頭結點另外用順序存儲結構存儲。每個單鏈表的頭結點另外用順序存儲結構存儲。二、鄰接表（鏈式）表示法二、鄰接表（鏈式）表示法7.2 圖的存儲結構圖的存儲結構16v1v2v3v5v4v40123413341420注注：鄰接表不唯一，因各個邊結點的鏈入順序是任意的。鄰接表不唯一，因各個邊結點的鏈入順序是任意的。v1v2v3v4v5231420例例1 1：無向圖的鄰接表無向圖的鄰接表7.2 圖的存儲結構圖的存儲結構17例例2 2：有向圖的鄰接表有向圖的鄰接表v1v2v3v4鄰接表鄰接表(出邊出邊)逆鄰接表逆鄰接表(入邊入邊)V4V3V2V123013210V4V3V2V1302032107.2 圖的存

15、儲結構圖的存儲結構188064125例例3 3：已知某網的鄰接（出邊）表，請畫出該網絡。已知某網的鄰接（出邊）表，請畫出該網絡。7.2 圖的存儲結構圖的存儲結構19遍歷定義：遍歷定義：從已給的圖中某一頂點出發，沿著一些邊，訪遍從已給的圖中某一頂點出發，沿著一些邊，訪遍 圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做遍歷實質：遍歷實質：找每個頂點的鄰接點的過程。找每個頂點的鄰接點的過程。圖的特點：圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些

16、邊又回到了曾經訪問過的頂點在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點解決思路：解決思路：可設置一個輔助數組可設置一個輔助數組 visited n ，用來標記每個被訪，用來標記每個被訪問過的頂點。它的初始狀態為問過的頂點。它的初始狀態為0 0，在圖的遍歷過程中，一旦某一個，在圖的遍歷過程中，一旦某一個頂點頂點i 被訪問，就立即改被訪問，就立即改 visited i為為1 1，防止它被多次訪問。，防止它被多次訪問。圖常用的遍歷：圖常用的遍歷：深度優先搜索廣度優先搜索 7.3 圖的遍歷圖的遍歷20一、深度優先搜索一、深度優先搜索( (Depth_First Search:DFSDF

17、S ) )遍歷步驟：從圖中某個頂點從圖中某個頂點v v出發，訪問此頂點，然后依次從出發，訪問此頂點，然后依次從v v的未被訪問的未被訪問的鄰接點出發深度優先遍歷圖，直至圖中所有和的鄰接點出發深度優先遍歷圖，直至圖中所有和v v有路徑相通的頂點都被有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。詳細歸納：詳細歸納：E在訪問圖中某一起始頂點在訪問圖中某一起始頂點 v 后，由后，由 v 出發

18、，訪問出發，訪問它的任一鄰接頂點它的任一鄰接頂點 w1；E再從再從 w1 出發，訪問出發，訪問與與 w1鄰接鄰接但還但還未被訪問未被訪問過的頂點過的頂點 w2；E然后再從然后再從 w2 出發，進行類似的訪問，出發，進行類似的訪問， E如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。為止。E接著，退回一步，接著，退回一步，退到前一次剛訪問過的頂點退到前一次剛訪問過的頂點，看是否還有其它未被訪問，看是否還有其它未被訪問 的鄰接頂點。的鄰接頂點。 如果有，如果有，則訪問此頂點，之后再從此頂點出發，進行與前述類似的訪問；則訪問此頂點，

19、之后再從此頂點出發，進行與前述類似的訪問； 如果沒有，如果沒有，就就再退回一步再退回一步進行搜索。重復上述過程，直到連通圖中所有頂進行搜索。重復上述過程，直到連通圖中所有頂 點都被訪問過為止。點都被訪問過為止。7.3 圖的遍歷圖的遍歷21起點起點應退回到應退回到V8V8，因為，因為V2V2已有標記已有標記v1v2v4v8v5v3v6v7124536起點7.3 圖的遍歷圖的遍歷22計算機如何實現計算機如何實現DFS？000000123456010000鄰鄰接接矩矩陣陣A輔助數組輔助數組 visited n 1 2 3 4 561 0 1 1 1 002 1 0 0 0 103 1 0 0 0 1

20、04 1 0 0 0 015 0 1 1 0 006 0 0 0 1 00110000111000起起點點1245361110101111101111112123125312312124126412棧棧的的變變化化4121227.3 圖的遍歷圖的遍歷23for( j=1; j=n; j+) if ( Av, j & ! visitedj ) DFS(A, n, j); return; / DFS/ DFSDFS算法如何編程？算法如何編程？DFS(A, n, v) visit（v）; visitedv=1;可以用遞歸算法！可以用遞歸算法！/Ann/Ann為鄰接矩陣，為鄰接矩陣，v v為起

21、始頂點為起始頂點( (編號）編號）/訪問（例如打印）頂點訪問（例如打印）頂點v v Av,j 1 有鄰接點有鄰接點visited n =0未訪問過未訪問過/訪問后立即修改輔助數組標志訪問后立即修改輔助數組標志/從從v v所在行從左到右搜索鄰接點所在行從左到右搜索鄰接點7.3 圖的遍歷圖的遍歷24二、廣度優先搜索二、廣度優先搜索( (Breadth_First Search：BFSBFS ) )基本思想：基本思想：仿樹的層次遍歷過程。仿樹的層次遍歷過程。遍歷步驟：遍歷步驟：在訪問了起始點在訪問了起始點v v之后，依次訪問之后，依次訪問 v v的鄰接點；然后再依的鄰接點；然后再依次（順序）訪問這些

22、點（下一層）中未被訪問過的鄰接點；直到所有頂次（順序）訪問這些點（下一層）中未被訪問過的鄰接點；直到所有頂點都被訪問過為止。點都被訪問過為止。廣度優先搜索是一種分層的搜索過程，每向前走一步廣度優先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優先搜索那樣有回退的可能訪問一批頂點，不像深度優先搜索那樣有回退的情況。情況。因此，廣度優先搜索不是一個遞歸的過程，其算法也因此，廣度優先搜索不是一個遞歸的過程，其算法也不是遞歸的。不是遞歸的。7.3 圖的遍歷圖的遍歷25起點起點v1v2v4v8v5v3v6v7起點起點3264159877.3 圖的遍歷圖的遍歷26起點起點12453665

23、4321234151516236計算機如何實現計算機如何實現BFS？-隊列隊列5432102front rear000000123456010000輔助數組輔助數組 visited n 1100102 1 5frontrearfrontrear1 53 4frontrear5 3 4frontrear 3 4front rear461111101111117.3 圖的遍歷圖的遍歷271. 求圖的生成樹求圖的生成樹2. 求最小生成樹求最小生成樹7.4 圖的連通性問題圖的連通性問題281. 求圖的生成樹（或生成森林）求圖的生成樹（或生成森林）生成樹：生成樹：是一個極小連通子圖，它含有圖中全部頂點，

24、但是一個極小連通子圖，它含有圖中全部頂點，但只有只有n-1n-1條邊。條邊。生成森林：生成森林：由若干棵由若干棵生成樹組成生成樹組成，含全部頂點，但構成這，含全部頂點，但構成這些樹的邊是最少的。些樹的邊是最少的。若對連通圖進行遍歷，得到的是圖的生成樹圖的生成樹若對非連通圖進行遍歷，得到的是圖的生成森林圖的生成森林深度優先搜索生成樹：由深度優先搜索得到的生成樹由深度優先搜索得到的生成樹廣度優先搜索生成樹：由廣度優先搜索得到的生成樹由廣度優先搜索得到的生成樹7.4 圖的連通性問題圖的連通性問題29例1 ：畫出下圖的生成樹DFS生生成成樹樹v0v1v2v4v3鄰接表0123413341420v4v3

25、v2v1v0231420v0v2v1v4v3BFS生生成成樹樹v0v1v3v2v4無向連通圖無向連通圖7.4 圖的連通性問題圖的連通性問題30DEABCFJLMGHIK例2：畫出下圖的生成森林（或極小連通子圖）求解步驟：求解步驟：Step1:Step1:先求出鄰接矩陣或鄰接表；先求出鄰接矩陣或鄰接表；Step2:Step2:寫出寫出DFSDFS或或BFSBFS結果序列；結果序列；Step3:Step3:畫出對應子圖或生成森林。畫出對應子圖或生成森林。這是一個無向非連通圖這是一個無向非連通圖下面選用下面選用鄰接表鄰接表方式來求方式來求深度深度優先搜索生成森林優先搜索生成森林生成森林的定義（對有向

26、或無向圖均生成森林的定義（對有向或無向圖均適用）：是若干棵適用）：是若干棵生成樹的集合生成樹的集合，含含全部頂點，但構成這些樹的邊或全部頂點，但構成這些樹的邊或弧弧是是最少的。最少的。7.4 圖的連通性問題圖的連通性問題31DEGHIKABCJLMDEABCFJLMGHIK5 512111098765432101201200437810661011126709121911112294710811MLKJIHGFEDCBA11F7.4 圖的連通性問題圖的連通性問題32目標：在網絡的多個生成樹中，尋找一個各邊權值之和最在網絡的多個生成樹中，尋找一個各邊權值之和最 小的生成樹。小的生成樹。2.2.求

27、最小生成樹求最小生成樹構造最小生成樹的準則v 必須只使用該網絡中的邊來構造最小生成樹；必須只使用該網絡中的邊來構造最小生成樹；v 必須使用且僅使用必須使用且僅使用n n-1-1條邊條邊來連接網絡中的來連接網絡中的n n個頂點個頂點；v 不能使用產生回路的邊。不能使用產生回路的邊。n個頂點的生成樹很多，需要從中選一棵個頂點的生成樹很多，需要從中選一棵代價最小代價最小的生成樹，即該樹的生成樹，即該樹各各邊的代價之和邊的代價之和最小。此樹便稱為最小生成樹最小。此樹便稱為最小生成樹MST。7.4 圖的連通性問題圖的連通性問題331普里姆(prim)算法基本思想：在圖中任取一個頂點在圖中任取一個頂點K

28、K作為開始點，令作為開始點，令U=kU=k，V=W-UV=W-U，其中，其中W W為為圖中所有頂點集，然后找一個頂點在圖中所有頂點集，然后找一個頂點在U U中，另一個頂點在中，另一個頂點在V V中的中的邊中最短的一條，找到后，將該邊作為最小生成樹的邊保存邊中最短的一條，找到后，將該邊作為最小生成樹的邊保存起來，并將該邊頂點全部加入起來，并將該邊頂點全部加入U U集合中，并從集合中，并從V V中刪去這些頂點，中刪去這些頂點，然后再重復此過程，直到然后再重復此過程，直到V V為空集止。為空集止。求MST最常用的算法vPrim（普里姆）算法（普里姆）算法 vKruskal（克魯斯卡爾）算法（克魯斯卡

29、爾）算法7.4 圖的連通性問題圖的連通性問題34（一）1U=1V=2,3,4,5,64U=1,3V=2,4,5,61（二）2U=1,3,6V=2,4,514（三）5U=1,3,6,4V=2,5142（四）3U=1,3,6,4,2V=51425（五）7.4 圖的連通性問題圖的連通性問題35算法的基本思想是：將圖中所有邊按權值遞增順序排列，算法的基本思想是：將圖中所有邊按權值遞增順序排列，依次選取權值較小的邊，但要求后面選取的邊不能與前面依次選取權值較小的邊，但要求后面選取的邊不能與前面選取的邊構成回路，若構成回路，則放棄該條邊，再去選選取的邊構成回路，若構成回路，則放棄該條邊，再去選后面權值較大

30、的邊，后面權值較大的邊，n個頂點的圖中，選夠個頂點的圖中，選夠n-1條邊即可。條邊即可。 2克魯斯卡爾 (Kruskal)算法1（一）選第1條邊21（二）選第2條邊7.4 圖的連通性問題圖的連通性問題36312（三）選第3條邊4123（四）選第4條邊51423（五）51423或選第5條邊（不能選（1，4）或（3，4）邊，會構成回路）7.4 圖的連通性問題圖的連通性問題37 AOV網網(Activity On Vertices)用頂點表示活動的網絡用頂點表示活動的網絡AOVAOV網定義：網定義：若用有向圖表示一個工程，在圖中若用有向圖表示一個工程，在圖中用頂點表示活動，用弧表用頂點表示活動，用弧

31、表示活動間的優先關系。示活動間的優先關系。Vi 必須先于活動必須先于活動Vj 進行。進行。則這樣的有向圖叫做用則這樣的有向圖叫做用頂點表示活動的網絡，簡稱頂點表示活動的網絡，簡稱 AOV。 AOE網網(Activity On Edges)用邊表示活動的網絡用邊表示活動的網絡AOEAOE網定義網定義：在帶權有向無環網中，：在帶權有向無環網中， 用有向邊表示一個工程中的活動，用用有向邊表示一個工程中的活動，用邊上權值表示活動持續時間，用頂點表示事件，邊上權值表示活動持續時間，用頂點表示事件，則這樣的有向圖叫做用邊則這樣的有向圖叫做用邊表示活動的網絡，簡稱表示活動的網絡，簡稱 AOE有兩種常用的活動

32、網絡（有兩種常用的活動網絡（ Activity Network）：）：有向無環圖是一個無環的有向圖，是描述一項工程或系統的進行過程的有效工具。幾乎所有的工程都可分為若干個稱做活動的子工程。7.5 有向無環圖及其應用有向無環圖及其應用38現代化管理中現代化管理中, , 通常我們把計劃、施工過程、生產流程、程序流程等都通常我們把計劃、施工過程、生產流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動。在整個工程實施過程中，有些活動開始是以它的所有前工程稱為活動。在整個工程實施過程中，有些活動開始是

33、以它的所有前序活動的結束為先決條件的，必須在其它有關活動完成之后才能開始，序活動的結束為先決條件的，必須在其它有關活動完成之后才能開始，有些活動沒有先決條件，可以安排在任意時間開始。有些活動沒有先決條件，可以安排在任意時間開始。AOVAOV網就是一種可網就是一種可以形象地反映出整個工程中各個活動之間前后關系的有向圖。以形象地反映出整個工程中各個活動之間前后關系的有向圖。AOV網的實際意義：例如，計算機專業學生的課程開設可看成是一個工程，每一門課程就是例如，計算機專業學生的課程開設可看成是一個工程，每一門課程就是工程中的活動，其中有些課程的開設有先后關系，有些則沒有先后關系，工程中的活動，其中有

34、些課程的開設有先后關系，有些則沒有先后關系，有先后關系的課程必須按先后關系開設，如開設數據結構課程之前必須有先后關系的課程必須按先后關系開設，如開設數據結構課程之前必須先學完程序設計基礎及離散數學，而開設離散數學則必須先并行學完數先學完程序設計基礎及離散數學，而開設離散數學則必須先并行學完數學、程序設計基礎課程。學、程序設計基礎課程。7.5 有向無環圖及其應用有向無環圖及其應用39課程代碼課程代碼課程名稱課程名稱先修課程先修課程C1高等數學高等數學C2程序設計基礎程序設計基礎C3離散數學離散數學C1，C2C4數據結構數據結構C2，C3C5高級語言程序設計高級語言程序設計C2C6編譯方法編譯方法

35、C5，C4C7操作系統操作系統C4，C9C8大學物理大學物理C1C9計算機原理計算機原理C8C1C2C3C4C5C6C7C9C8學生開設課程的AOV圖7.5 有向無環圖及其應用有向無環圖及其應用40一、拓撲排序1、定義： 給出有向圖給出有向圖G=(V,E)G=(V,E)，對于，對于V V中的頂點的線性序列中的頂點的線性序列(v(v1 1,v,v2 2,.,v,.,vn n) )，如果滿足如下條件：若在，如果滿足如下條件：若在G G中從頂點中從頂點 v vi i 到到v vj j有一條路經，則在序列中頂點有一條路經，則在序列中頂點v vi i必在頂點必在頂點v vj j之前；則稱該序列之前；則稱

36、該序列為為G G的一個的一個拓撲序列拓撲序列。構造有向圖的一個拓撲序列的過程稱為構造有向圖的一個拓撲序列的過程稱為拓撲排序拓撲排序。7.5 有向無環圖及其應用有向無環圖及其應用412、拓撲序列的實際意義: 如果按照拓撲序列中的頂點次序進行每一項活動如果按照拓撲序列中的頂點次序進行每一項活動, ,就能夠保證在就能夠保證在開始每一項活動時開始每一項活動時, ,他的所有前驅活動均已完成他的所有前驅活動均已完成, ,從而使整個工程順從而使整個工程順序執行序執行. .3、說明(1)(1)在在AOVAOV網中，若不存在回路，則所有活動可排成一個線性序列網中，若不存在回路，則所有活動可排成一個線性序列, ,

37、使得使得每個活動的所有前驅活動都排在該活動的前面每個活動的所有前驅活動都排在該活動的前面, ,那么該序列為拓撲序列。那么該序列為拓撲序列。(2)(2)拓撲序列拓撲序列不是唯一的不是唯一的。7.5 有向無環圖及其應用有向無環圖及其應用424、拓撲排序方法（1 1）在）在AOVAOV網中選一個入度為網中選一個入度為0 0的頂點（沒有前驅）且輸出之；的頂點（沒有前驅）且輸出之；（2 2）從）從AOVAOV網中刪除此頂點及該頂點發出來的所有有向邊；網中刪除此頂點及該頂點發出來的所有有向邊；（3 3）重復（）重復（1 1）、（）、（2 2）兩步，直到）兩步，直到AOVAOV網中所有頂點都被輸出或網中不存

38、在網中所有頂點都被輸出或網中不存在 入度為入度為0 0的頂點。的頂點。C1C2C3C4C5C6C7C9C8C2C3C4C5C6C7C9C8輸出C17.5 有向無環圖及其應用有向無環圖及其應用43C3C4C5C6C7C9C8C4C5C6C7C9C8C5C6C7C9C8C6C7C9C8輸出C2輸出C3輸出C4輸出C57.5 有向無環圖及其應用有向無環圖及其應用44C7C9C8C7C9C7輸出C6輸出C8輸出C9（C1,C2,C3,C4,C5,C6,C8,C9,C7）7.5 有向無環圖及其應用有向無環圖及其應用45二、關鍵路徑( (一一) )、AOEAOE網概念網概念1.1.定義定義 若在帶權的有向

39、圖中若在帶權的有向圖中, ,以頂點表示事件以頂點表示事件, ,有向邊表示活動有向邊表示活動, ,邊上的權值表邊上的權值表示完成該活動的開銷示完成該活動的開銷( (如該活動所需的時間如該活動所需的時間),),則稱此帶權的有向圖為用邊則稱此帶權的有向圖為用邊表示活動的網絡表示活動的網絡, ,簡稱簡稱AOEAOE網。網。2.2.說明說明(1) AOV(1) AOV網與網與AOEAOE網有密切關系又有不同。網有密切關系又有不同。如果用他們表示工程，如果用他們表示工程，AOVAOV網網表示各個子工程之間的優先關系，是定性關系；在表示各個子工程之間的優先關系，是定性關系；在AOEAOE網中還要體現完網中還

40、要體現完成各個子工程的確切時間，是定量關系。成各個子工程的確切時間，是定量關系。（2 2）對于）對于AOEAOE網，我們關心的問題是：網，我們關心的問題是： （A A）完成整個工程至少需要多少時間？）完成整個工程至少需要多少時間？ （B B）哪些活動是關鍵活動，哪些活動的進度是影響整個工程進度的）哪些活動是關鍵活動，哪些活動的進度是影響整個工程進度的關鍵？關鍵？7.5 有向無環圖及其應用有向無環圖及其應用46（2 2）在）在AOEAOE網中，只有在某頂點所代表的事件發生后，從該頂點出發的網中，只有在某頂點所代表的事件發生后，從該頂點出發的各有向邊所代表的活動才能開始。只有在進入每頂點的各有向邊

41、所代表各有向邊所代表的活動才能開始。只有在進入每頂點的各有向邊所代表的活動都已經結束后，該頂點所代表的事件才能發生。的活動都已經結束后，該頂點所代表的事件才能發生。（3 3）在一個表示工程的）在一個表示工程的AOEAOE網中，應該不存在回路，網中僅存在一個入網中，應該不存在回路，網中僅存在一個入度為零的頂點，稱作開始頂點，它表示了整個工程的開始；網中僅存在度為零的頂點，稱作開始頂點，它表示了整個工程的開始；網中僅存在一個出度為零的頂點，稱為結束頂點，它表示整個工程的結束。一個出度為零的頂點，稱為結束頂點，它表示整個工程的結束。a5=8v1v2v4v5v8v10v7v6v3v9a1=3a2=2a

42、3=6a4=3a6=4a7=2a8=7a9=4a10=6a11=9a12=6a13=5a14=4a15=87.5 有向無環圖及其應用有向無環圖及其應用47(二)、關鍵路徑有關術語1.路徑長度2.關鍵路徑AOEAOE網中一條路徑的長度是該路徑上個活動所需時間的總和。網中一條路徑的長度是該路徑上個活動所需時間的總和。AOEAOE網中網中, ,從開始頂點到結束頂點之間從開始頂點到結束頂點之間路徑長度中的最大路徑路徑長度中的最大路徑為關鍵為關鍵路徑。由于路徑。由于AOEAOE網中某些子工程（活動）可以同時進行，要保證每個網中某些子工程（活動）可以同時進行，要保證每個子工程都能完成，完成該工程的最少時間

43、就是該工程子工程都能完成，完成該工程的最少時間就是該工程AOEAOE網的關鍵路網的關鍵路徑長度。徑長度。3.事件的最早發生時間4.活動的最早開始時間 事件事件vivi的最早發生時間的最早發生時間ve(i)ve(i)是從開始頂點是從開始頂點v v到到vivi的最長路徑長度。的最長路徑長度。活動活動ajaj的最早開始時間的最早開始時間e(j)e(j)是該活動的起點所表示的事件最早發生時是該活動的起點所表示的事件最早發生時間間, ,如果由邊如果由邊(vi,vk)(vi,vk)表示活動表示活動aj,aj,則有則有e(j)=ve(i)e(j)=ve(i)。7.5 有向無環圖及其應用有向無環圖及其應用48

44、5.事件的最遲發生時間6.活動的最遲開始時間 事件事件vkvk的最遲發生時間的最遲發生時間vl(k)vl(k)是在不推遲整個工程完成是在不推遲整個工程完成( (即保證結束頂點即保證結束頂點vnvn在在ve(n)ve(n)時刻發生時刻發生) )的前提下的前提下, ,該事件最遲必須發生的時間。該事件最遲必須發生的時間。活動活動ajaj的最遲開始時間的最遲開始時間l(j)l(j)是該活動的終點所表示的事件最遲發生時是該活動的終點所表示的事件最遲發生時間與該活動的所需時間之差。間與該活動的所需時間之差。7. 時間余量8.關鍵活動 活動活動ajaj的的 l(j)-e(j)l(j)-e(j)是該活動完成的

45、時間余量。它是在不增加完成整是該活動完成的時間余量。它是在不增加完成整個工程所需時間的情況下，活動個工程所需時間的情況下，活動ajaj可以拖延的時間。可以拖延的時間。當一活動的時間余量當一活動的時間余量=0=0，說明該活動必須如期完成，否則就會拖延完成，說明該活動必須如期完成，否則就會拖延完成整個工程的進度。若活動整個工程的進度。若活動ajaj的時間余量的時間余量=0=0，則稱該活動為關鍵活動。，則稱該活動為關鍵活動。當時間余量當時間余量0 0，活動，活動ajaj不是關鍵活動，只要拖延的時間不超過時間余不是關鍵活動，只要拖延的時間不超過時間余量，就不會影響整個工程的進度；但如果拖延的時間超過時

46、間余量，則量，就不會影響整個工程的進度；但如果拖延的時間超過時間余量，則關鍵活動就可能發生變化。關鍵活動就可能發生變化。7.5 有向無環圖及其應用有向無環圖及其應用49(三)、關鍵路徑的計算方法ve(0) = 0ve(j) = max ve(i) + 上的權上的權 為所有到達為所有到達vj的有向邊的有向邊1.求事件的最早發生時間ve(j)關鍵路徑上的活動是關鍵活動。關鍵活動就滿足e(i)=l(i)由弧表示的活動ai的最早開始時間e(i)=ve(j)7.5 有向無環圖及其應用有向無環圖及其應用50vl (n) = ve(n)vl (i) = min vl(j) - 上的權上的權 為所有到達為所有

47、到達vj的有向邊的有向邊2.求事件的最遲發生時間vl(i)由弧表示的活動ai的最遲開始時間l(i)=vl(k) - 上的權上的權7.5 有向無環圖及其應用有向無環圖及其應用51vevl2517172011139230v10v9v8v7v6v5v4v3v2v1ela10a9a8a7a6a5a4a3a2a1a15a14a13a12a111717201111131329932300251721201114943002366109417141111202117a5=8v1v2v4v5v8v10v7v6v3v9a1=3a2=2a3=6a4=3a6=4a7=2a8=7a9=4a10=6a11=9a12=6

48、a13=5a14=4a15=87.5 有向無環圖及其應用有向無環圖及其應用52關鍵活動:a1,a3,a7,a11,a12,a13,a15v1v2v4v10v7v6v9a1=3a3=6a7=2a11=9a12=6a13=5a15=8關鍵路徑:（ v1, v2, v4, v6, v7, v10 ）和（ v1, v2, v4, v6, v9, v10 ）a5=8v1v2v4v5v8v10v7v6v3v9a1=3a2=2a3=6a4=3a6=4a7=2a8=7a9=4a10=6a11=9a12=6a13=5a14=4a15=87.5 有向無環圖及其應用有向無環圖及其應用53典型用途：交通問題。如：城市

49、交通問題。如：城市A A到城市到城市B B有多條線路，但有多條線路，但每條線路的交通費（或所需時間）不同，那么，如何選擇每條線路的交通費（或所需時間）不同，那么，如何選擇一條線路，使總費用（或總時間）最少？一條線路，使總費用（或總時間）最少？問題抽象：在帶權有向圖中在帶權有向圖中A A點（源點）到達點（源點）到達B B點（終點）的點（終點）的多條路徑中，尋找一條各邊權值之和最小的路徑，即最短多條路徑中，尋找一條各邊權值之和最小的路徑，即最短路徑。路徑。（注：最短路徑與最小生成樹不同，路徑上不一定包含（注：最短路徑與最小生成樹不同，路徑上不一定包含n n個頂點）個頂點）兩種常見的最短路徑問題：1

50、、 從某個頂點到其余各頂點的最短路徑從某個頂點到其余各頂點的最短路徑Dijkstra(Dijkstra(迪杰斯特拉迪杰斯特拉) )算法算法2 2、每一對頂點之間的最短路徑、每一對頂點之間的最短路徑Floyd(弗洛伊德弗洛伊德)算法算法7.6 最短路徑最短路徑54單源點最短路徑：給定一個出發點給定一個出發點( (單源點單源點) )和一個有向網和一個有向網G=(V,E),G=(V,E),求出源點求出源點V1V1到其它各頂點之間的最短路徑。到其它各頂點之間的最短路徑。v1v2v5v3v6v4v7915126423851116從從v1到到v7共有共有5條路徑條路徑:v1、v2、v5、v7：20v1、v

51、4、v2、v5、v7：14v1、v2、v7：23v1、v4、v2、v7：17v1、v4、v6、v7：267.6 最短路徑最短路徑55二、算法的具體步驟：（1 1）初始時，）初始時，S S只包含源點，只包含源點，S=vS=v，v v的距離為的距離為0 0。U U包含除包含除v v外的其他外的其他頂點，頂點，U U中頂點的距離為頂點的權或中頂點的距離為頂點的權或 。（2 2）從）從U U中選取一個距離最小的頂點中選取一個距離最小的頂點k k，把，把k k加入到加入到S S中中（3 3）以）以k k 作為新考慮的中間點，修改作為新考慮的中間點，修改U U中各頂點的距離。中各頂點的距離。（4 4）重復

52、步驟（）重復步驟（2 2）、（）、（3 3）直到所有頂點都包含在）直到所有頂點都包含在S S中。中。一、算法的基本思想:把圖中頂點集合分成兩組，第一組為集合把圖中頂點集合分成兩組，第一組為集合S S，存放已求出其最短路徑的頂，存放已求出其最短路徑的頂點，第二組為尚未確定最短路徑的頂點集合是點，第二組為尚未確定最短路徑的頂點集合是V-SV-S（用（用U U表示），其中表示），其中V V為為網中所有頂點集合。按最短路徑長度遞增的順序逐個把網中所有頂點集合。按最短路徑長度遞增的順序逐個把U U中的頂點加到中的頂點加到S S中，直到中，直到S S中包含全部頂點，而中包含全部頂點，而U U為空。為空。7

53、.6 最短路徑最短路徑1383032V2:813-133032V1:13-13302220V3:13-192220V4:19終點終點 從從V0到各終點的最短路徑及其長度到各終點的最短路徑及其長度V1V2V3V4V5V6Vj-2120V6:20V5V1V6V4V3V2V0856230137173297.6 最短路徑最短路徑571、已知如圖所示的有向圖，請給出該圖的（1）每個頂點的入/出度。（2）鄰接矩陣（3）鄰接表（4）逆鄰接表（5）強連通分量156324練習練習582、請對下圖的無向帶權圖：（1）寫出它的鄰接矩陣;（2）寫出它的鄰接表。練習練習593、已知圖G的鄰接矩陣為 0 1 0 1 0

54、0 1 1 1 0 1 0 0 1 1 0問(1)該圖是有向圖還是無向圖?為什么? (2)各結點的度是多少?練習練習604、已知某有向圖的鄰接表如下，求出每個頂點的入度和出度。練習練習615、已知如圖所示的圖，若從頂點a出發，按深度搜索法進行遍歷，則可能得到的一種頂點序列是 ；若按廣度搜索法進行遍歷，則可能得到的一種頂點序列是 。abefcdA. a,b,e,c,d,f B. a,c,f,e,b,dC. a,e,b,c,f,d D. a,e,d,f,c,bA. a,b,c,e,d,f B. a,b,c,e,f,dC. a,e,b,c,f,d D. a,c,f,d,e,b練習練習626、已知一有

55、向圖的鄰接表如下圖所示，若從頂點1出發，求其深度優先遍歷序列和廣度優先遍歷序列。12 34 53244524練習練習637、對于如下所示的有向圖，試給出： （1）鄰接矩陣 （2）從出發的深度優先遍歷序列（3）從出發的廣度優先遍歷序列 152364練習練習648、已知以二維數組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發遍歷所得的深度優先生成樹和廣度優先生成樹。1 2 3 4 5 6 7 8 9 100 0 0 0 0 0 1 0 1 00 0 1 0 0 0 1 0 0 00 0 0 1 0 0 0 1 0 00 0 0 0 1 0 0 0 1 00 0 0 0 0 1 0 0 0 1

56、1 1 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 0 11 0 0 1 0 0 0 0 1 00 0 0 0 1 0 1 0 0 11 0 0 0 0 1 0 0 0 0 12345678910練習練習659、給出圖G：（1）畫出G的鄰接表；（2）根據畫出的鄰接表，以頂點為根，畫出G的深度優先 生成樹和廣度優先生成樹。31057842169圖G練習練習6610、考慮右圖：(1)從頂點A出發，求它的深度優先遍歷生成樹(2)從頂點E出發，求它的廣度優先遍歷生成樹(3)根據普利姆(Prim) 算法，求它的最小生成樹EABGCDF536141325練習練習6711、請對下面的無向帶

57、權圖（1）寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹。（2）寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。abefcdgh43555597654623練習練習6812、列出圖中全部可能的拓撲有序序列。213546練習練習6913、已知一圖如圖1所示：（1）寫出該圖的鄰接矩陣；（2）寫出全部拓撲排序序列；v7v8v6v5v31033645122v1v2v4圖1練習練習7014、求下面的AOE網絡的關鍵路徑和關鍵活動。6aABDFGICHEJwK1634312781165211069941210834練習練習1133434317610 713 3 834192624200vevlIHGFE

58、DCBAaJKw312244442231aABDFGICHEJwK16343127811652110699412108346 el el 0 0 0 0 0 0 1 6 3 3 3 4 4 3 3 1 17 13 13 13 22 31 31 34 191816 4 0 6202419262523 8 23 3 7 26 22 27 13 22 31 32 34練習練習7215、利用Dijkstra算法求下圖中從頂點a到其他各頂點的最短路徑。eagcfdb12531049461528練習練習15212c:215-12106f:615-1110-16e:1015-11-16d:1115-14g:

59、14eagcfdb12531049461528終點終點 從從a到各終點的最短路徑及其長度到各終點的最短路徑及其長度bcdefgVj15- v:15練習練習74教學要求：教學要求：1 1、理解圖的基本概念，熟悉圖的各種存儲結構；、理解圖的基本概念，熟悉圖的各種存儲結構；2 2、熟練掌握圖的兩種搜索路徑的方法；、熟練掌握圖的兩種搜索路徑的方法；3 3、掌握構造生成樹、最小生成樹的方法；、掌握構造生成樹、最小生成樹的方法；4 4、掌握求活動網絡的拓撲排序的方法；、掌握求活動網絡的拓撲排序的方法； 5 5、掌握求解關鍵路徑的方法；、掌握求解關鍵路徑的方法；6 6、掌握用、掌握用DijkstraDijk

60、stra方法求解單源最短路徑問題。方法求解單源最短路徑問題。第7章 圖751、寫出下圖的鄰接矩陣和鄰接表，并畫出以頂點1出發進行深度優先遍歷所得到的深度優先生成樹，以頂點2出發進行廣度優先遍歷得到的廣度優先生成樹。123452、用兩種方法求下圖的最小生成樹。03124565517354623、寫出下圖所有的拓撲序列。ABCDEF作業作業764、求下圖的關鍵路徑。5、求下圖從頂點A出發到達各點的最短路徑。ABCDE101852252123456215101119654作業作業771 1用鄰接矩陣法存儲圖時，所占用的連續空間大小僅于圖中結點個數用鄰接矩陣法存儲圖時，所占用的連續空間大小僅于圖中結點個數有關