1、第五章 圖,圖（Graph）是一種較線性表和樹更為復雜的非線性結構。在圖結構中，對結點（圖中常稱為頂點）的前趨和后繼個數不加限制，即結點之間的關系是任意的。圖中任意兩個結點之間都可能相關。圖狀結構可以描述各種復雜的數據對象。 圖的應用極為廣泛，特別是近年來的迅速發展，已經滲透到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數學的其它分支中。,圖狀結構的實際背景 在城市之間建立通訊網絡，使得其中的任意兩個城市之間有直接或間接的通訊線路，假設已知每對城市之間通訊線路的造價，要求找出一個造價最低的通訊網絡。,城市航線網,計算機網絡,第五章 圖 5.1 基本概念 5.2 圖的存儲結構 5.3

2、 圖的遍歷 5.4 拓撲排序 5.5 關鍵路徑 5.6 最短路徑 5.7 最小支撐樹,定義5.1：圖G由兩個集合V和E組成，記為G=(V, E)；其中 V 是頂點的有限集合，E 是連接 V 中兩個不同頂點的邊的有限集合。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。 如果E中的頂點對是有序的，即E中的每條邊都是有方向的，則稱G為有向圖。如果頂點對是無序對，則稱G是無向圖。,5.1 圖的基本概念,定義5.2 若G = (V, E)是有向圖，則它的一條有向邊是由V中兩個頂點構成的有序對，亦稱為弧，記為，其中w是邊的始點，又稱弧尾；v是邊的終點，又稱弧頭。,有向圖 G=（V，E） V= v

3、1，v2，v3，v4 E=,無向圖,G=(V,E) V=V1, V2, V3, V4 ,V5 E=(V1, V4 ), (V1, V2), (V2, V3 ), (V2, V5 ), (V3, V4 ), (V3, V5 ) ,定義5.3 在無向圖中，若兩個頂點w和v之間存在一條邊(w, v)，則稱w, v是相鄰的，二者互為鄰接頂點。 在有向圖中，若存在一條邊，則稱頂點w鄰接到頂點v，頂點v鄰接自頂點w.,定義5.4 由于E是邊的集合，故一個圖中不會多次出現一條邊。若去掉此限制，則由此產生的結構稱為多重圖。圖 (c)就是一個多重圖。,(a) (b) (c),定義5.5 設G是無向圖，vV(G)

4、，E(G)中以v為端點的邊的個數，稱為頂點的度。若G是有向圖，則v的出度是以v為始點的邊的個數，v的入度是以v為終點的邊的個數。 有向圖中，以某頂點為弧頭的弧的數目稱為該頂點的入度。以某頂點為弧尾的弧的數目稱為該頂點的出度。 頂點的度=入度+出度。,設圖G(可以為有向或無向圖)共有n個頂點， e條邊，若頂點vi的度數為D(vi)，則,因為一條邊關聯兩個頂點，而且使得這兩個頂點的度數分別增加1。因此頂點的度數之和就是邊的兩倍。,定義5.6 設G是圖，若存在一個頂點序列 使得 或 屬于E(G)，則稱vp到vq存在一條路徑，其中vp 稱為起點，vq稱為終點。 路徑的長度是該路徑上邊的個數。如果一條路

5、徑上除了起點和終點可以相同外，再不能有相同的頂點，則稱此路徑為簡單路徑。如果一條簡單路徑的起點和終點相同，且路徑長度大于等于2，則稱之為簡單回路。,圖(a)中，v1到v3之間存在一條路徑v1, v2, v5, v4, v3，同時這也是一條簡單路徑；v1, v2, v5, v4, v3, v1是一條簡單回路。,(a) (b) (c),路徑：v1 v3 v4 v3 v5 簡單路徑：v1 v3 v5 簡單回路：v1 v2 v3 v1,路徑：v1 v3 v2 v4 v3 v2 簡單路徑：v1 v3 v2 簡單回路：v1 v3 v2 v1,定義5.7 設G，H是圖，如果V(H) V(G)，E(H) E(

6、G)，則稱H是G的子圖，G是H的母圖。如果H是G的子圖，并且V(H) = V(G)，則稱H為G的支撐子圖。,完全圖 ：有向完全圖(邊數n*(n-1) 無向完全圖(邊數1/2*n*(n-1),定義5.8 設G是圖，若存在一條從頂點vi到頂點vj的路徑，則稱vi與vj可及(連通)。若G為無向圖，且V(G)中任意兩頂點都可及，則稱G為連通圖。若G為有向圖，且對于V(G)中任意兩個不同的頂點vi和vj ， vi與vj可及， vj與vi也可及，則稱G為強連通圖。 也可以定義“弱連通圖”的概念，即在任何頂點u和v之間，至少存在一條從u到v的路徑或者存在一條從v到u的路徑。,定義5.10 對于G的一個連通子

7、圖GK，如果不存在G的另一個連通子圖G，使得V(GK)V(G)，則稱GK為G的連通分量。 無向圖G的極大連通子圖稱為G的連通分量。,(a) (b) (c),(d) (e),一個圖的連通子圖,e是a的連通分量,連通分量,連通分量,有時候，圖不僅要表示出元素之間是否存在某種關系，同時還需要表示與這一關系相關的某些信息。 例如在計算機網絡對應的圖中，頂點表示計算機，頂點之間的邊表示計算機之間的通訊鏈路。實際中，為了管理計算機網絡，我們需要這個圖包含更多的信息，例如每條通訊鏈路的物理長度、成本和帶寬等信息。為此，我們為傳統圖中的每條邊添加相應的數據域以記錄所需要的信息。,定義5.11 設G = (V,

8、 E)是圖，若對圖中的任意一條邊l，都有實數w(l)與其對應，則稱G為權圖，記為G = (V, E, w)。記w(u,v)表示w(u,v)或w()，規定： uV, 有w(u,u)=0或w()=0 u,vV, 若(u,v)E(G)或E(G) 則w(u,v)=或w()=,定義5.12 若 是權圖G中的一條路徑，則 稱為加權路徑 的長度或權重。 權通常用來表示從一個頂點到另一個頂點的距離或費用。,無向圖 有向圖 邊 端點 弧 弧頭 弧尾 相鄰的 鄰接到 鄰接自 度 出度 入度 連通圖 強連通圖,第五章 圖 5.1 基本概念 5.2 圖的存儲結構 5.3 圖的遍歷 5.4 拓撲排序 5.5 關鍵路徑

9、5.6 最短路徑 5.7 最小支撐樹,鄰接矩陣 鄰接表(逆鄰接表),1、 圖的存儲結構,用順序方式或鏈接方式存儲圖的頂點表v0,v1,vn-1 ,圖的邊用nn階矩陣A =(aij)表示，A的定義如下： （a）若圖為權圖，aij對應邊的權值； （b）若圖為非權圖，則 （1） aii=0； （2） aij=1，當ij且或(vi,vj)存在時； （3）aij=0，當ij且或(vi,vj)不存在時。 稱矩陣A為圖的鄰接矩陣。,1、鄰接矩陣,例1無向圖的鄰接矩陣 無向圖的鄰接矩陣是對稱陣。,例2有向圖的鄰接矩陣,例3權圖的鄰接矩陣,借助鄰接矩陣，可以很容易地求出圖中頂點的度。 無向圖 鄰接矩陣的第i行（

10、或第i列）的非零元素的個數是頂點Vi的度。 有向圖 鄰接矩陣第i行的非零元素的個數為頂點Vi的出度；第i列的非零元素的個數為頂點Vi的入度。,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0,2、鄰接表 鄰接表是圖的一種鏈式存儲結構。對圖的每個頂點建立一個單鏈表（n個頂點建立n個單鏈表），第i個單鏈表中的結點包含頂點Vi的所有鄰接頂點。由順序存儲的頂點表和鏈接存儲的邊鏈表構成的圖的存儲結構被稱為鄰接表。,例1無向圖的鄰接表 頂點的結構 非權圖中邊結點結構 對于用鄰接表存儲的無向圖，

11、每條邊對應兩個邊結點； 根據鄰接表，可以統計出無向圖中每個頂點的度。,例2有向圖的鄰接表 對于用鄰接表存儲的有向圖，每條邊只對應一個邊結點； 根據鄰接表，可以統計出有向圖中每個頂點的出度。但是，如果要統計頂點的入度，每統計一個頂點，就要遍歷所有的邊結點，其時間復雜度為O(e)(e為圖中邊的個數)，從而統計所有頂點入度的時間復雜度為O(ne)(n為圖的頂點個數)。,例3有向圖的逆鄰接表 建立逆鄰接表(頂點的指向關系與鄰接表恰好相反)，根據逆鄰接表，很容易統計出圖中每個頂點的入度。,例4 權圖的鄰接表,權圖中邊結點結構,采用鄰接矩陣還是用鄰接表來存儲圖，要視對給定圖實施的具體操作而定。 對于邊很多

12、的圖(也稱稠密圖)，適于用鄰接矩陣存儲，因為占用的空間少。 而對于頂點多而邊少的圖(也稱稀疏圖)，若用鄰接矩陣存儲，對應的鄰接矩陣將是一個稀疏矩陣，存儲利用率很低。因此，頂點多而邊少的圖適于用鄰接表存儲。,鄰接矩陣存儲的圖類Graph_Matrix 鄰接表存儲的圖類Graph_List,2、 圖的實現,1. 用鄰接矩陣存儲的圖類 Graph_Matrix類聲明 const int MaxGraphSize = 256 ; / 圖的最大頂點個數 const int MaxWeight = 1000 ; /邊的最大權值 template class Graph_Matrix private: SL

13、List VertexList ; /頂點表 int edge MaxGraphSize MaxGraphSize ; /鄰接矩陣 int graphsize ; /當前頂點數,public: /I. 構造函數與析構函數 Graph_Matrix( ) ; Graph_Matrix( ) ; /II. 圖的維護函數 int GraphEmpty(void) const /檢測圖是否為空 int GraphFull(void) const ; /檢測圖是否已滿，即頂點個數是否越界 int NumberOfVertices( void ) const ;/返回圖的頂點個數 int NumberOf

14、Edges( void ) const ; /返回圖的邊個數 int GetWeight( const int v1, const int v2 ) ; / 返回指定邊的權值 int* /返回序號為v1的頂點相對于序號為v2的頂點的下一個鄰接頂點的序號,void InsertVertex( const int ,/ 構造函數, 創建一個圖 Graph_Matrix : Graph_Matrix () cin graphsize; for( int i = 0 ; i edgeij; ,/ 取得序號為v的頂點的第一個鄰接頂點的序號 int Graph_Matrix :GetFirstNeighb

15、or( const int v ) if (v = = -1) return -1; for( int i = 0 ; i 0 / 若v沒有鄰接頂點，則返回-1 ,/取得頂點v1相對于v2的下一個鄰接頂點的序號 int Graph_Matrix :GetNextNeighbor( const int v1 , const int v2 ) if (v1 = = -1 | v2= = -1) return -1; for( int i = v2 + 1 ; i 0 /若在v2之后沒有與v1鄰接的頂點，則返回-1 ,刪除頂點Vertex 算法思想：不僅要從頂點表中刪除該頂點，還需要刪除該頂點所發出

16、的邊以及所有的入邊，即在鄰接矩陣中刪除相應的行和列。,2. 用鄰接表存儲的圖類Graph_List,2. 用鄰接表存儲的圖類Graph_List / 邊結點的結構體 struct Edge friend class Graph_List ; int VerAdj ; / 鄰接頂點序號，從0開始編號 int cost ; / 邊的權值 Edge *link ; / 指向下一個邊結點的指針 ;,權圖中邊結點結構,/ 頂點表中結點的結構體 struct Vertex friend class Graph_List; int VerName;/ 頂點的名稱 Edge *adjacent;/ 邊鏈表的頭

17、指針 ,頂點的結構,/采用鄰接表存儲的Graph_List類定義 class Graph_List private: Vertex *Head; / 頂點表頭指針 int graphsize; / 圖中當前頂點的個數 public: / I. 圖的構造函數和析構函數 Graph_List ( ); Graph_List ( ); / II. 圖的維護函數 與Graph_Matrix類中的維護函數相同。 / III. 圖的基本算法 與Graph_Matrix類中的基本算法相同。 ;,/ 求序號為v的頂點的第一個鄰接頂點的序號 int Graph_List: GetFirstNeighbor( c

18、onst int v ) if ( v = = -1 ) return -1; Edge *p = Headv.adjacent ; if (p != NULL) return pVerAdj ; else return -1; ,Head,/ 求序號為v1的頂點相對于序號為v2的頂點的下一個鄰接頂點的序號 int Graph_List : GetNextNeighbor( const int v1 , const int v2 ) if ( v1 != -1 ,第五章 圖 5.1 基本概念 5.2 圖的存儲結構 5.3 圖的遍歷 5.4 拓撲排序 5.5 關鍵路徑 5.6 最短路徑 5.7

19、最小支撐樹,從已給的連通圖中某一頂點出發，沿著一些邊訪遍圖中所有頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷 ( Graph Traversal )。 圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。 為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數組 visited ，它的初始狀態為 0，在圖的遍歷過程中，一旦某一個頂點 i 被訪問，就立即讓 visitedi 為 1，防止它被多次訪問。,5.3.1 深度優先遍歷 深度優先遍歷又被稱為深度優先搜索 DFS ( Depth First Search ) 基本思想: D

20、FS 在訪問圖中某一起始頂點 v 后，由 v 出發，訪問它的任一鄰接頂點 w1；再從 w1 出發，訪問與 w1鄰接但還沒有訪問過的頂點 w2；然后再從 w2 出發，進行類似的訪問， 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。,深度優先搜索DFS ( Depth First Search ),深度優先搜索的示例,1. 遞歸算法/P140 算法DepthF

21、irstSearch (v, visited) /* 圖的深度優先遍歷的遞歸算法*/ DFSearch1初始化 PRINT(v). visitedv 1. p adjacent(Headv) . DFSearch2深度優先遍歷圖 WHILE pDO ( IF visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visited) . p link(p) . ),算法 DFS_Main( ) visited = new intgraphsize ;/ 為輔助數組申請空間 for( int k = 0 ; k graphsize ; k + + )

22、visitedk = 0 ; / 數組初始化 / 從序號為0的頂點出發，深度優先遍歷圖 DepthFirstSearch( 0 , visited ) ; delete visited ; / 釋放輔助數組空間 ,DFSearch1初始化 PRINT(v). visitedv 1. p adjacent(Headv) . DFSearch2深度優先遍歷圖 WHILE p DO ( IF visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visited) . p link(p) . ),可以利用堆棧實現深度優先遍歷的非遞歸算法。 堆棧中存放已

23、訪問結點的未被訪問的鄰接頂點，每次彈出棧頂元素時，如其未被訪問，則訪問該頂點，并檢查當前頂點的邊鏈表，將其未被訪問的鄰接頂點入棧，循環進行。,2. 迭代算法,首先將所有頂點的visited值置為0, 初始頂點壓入堆棧； 檢測堆棧是否為空。若堆棧為空，則迭代結 束；否則，從棧頂彈出一個頂點v； 如果v未被訪問過，則訪問v，將visitedv值更新為1，然后根據v的鄰接頂點表，將v的未被訪問的鄰接頂點壓入棧，執行步驟 。,算法DFS (Head, v , visited. visited) /* 圖的深度優先遍歷的非遞歸算法*/ DFS1初始化 CREATS(S) . /*創建堆棧 S */ FO

24、R i = 1 TO n DO visitedi 0. S v. /* 將v壓入棧中 */ DFS2利用堆棧S深度優先遍歷圖 WHILE NOT(ISEMTS(S) DO /* 當S不空時 */ ( v S. /*彈出堆棧頂元素 */ IF visitedv = 0 THEN ( PRINT(v) . visitedv 1. p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN S VerAdj(p) . p link(p). ) ) ),DFS2利用堆棧S深度優先遍歷圖 WHILE NOT(ISEMTS(S) DO /*

25、當S不空時 */ ( v S. IF visitedv = 0 THEN ( PRINT(v) . visitedv 1. p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN S VerAdj(p) . p link(p). ) ) ),算法分析,圖中有 n 個頂點，e 條邊。 如果用鄰接表表示圖，沿頂點的adjacent可以找到某個頂點v 的所有鄰接頂點w。由于總共有2e 個邊結點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復雜性為O(n+e)。 如果用鄰接矩陣表示圖，則查找每一個頂點的所有

26、的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。,非連通圖需要多次調用深度優先遍歷算法 For i=0 to n-1 DO visitedi 0. For j=0 to n-1 DO IF visitedj=0 THEN DepthFirstSearch (vj, visited),5.3.2 廣度優先遍歷 基本思想： 首先訪問初始點頂點v0，之后依次訪問與v0鄰接的全部頂點w1，w2，.，wk。然后，再順次訪問與w1，w2，.，wk鄰接的尚未訪問的全部頂點，再從這些被訪問過的頂點出發，逐個訪問與它們鄰接的尚未訪問過的全部頂點。依此類推，直到連通圖中的所有頂點全部訪問完為

27、止。,廣度優先搜索BFS ( Breadth First Search ),廣度優先搜索的示例,廣度優先搜索過程 廣度優先生成樹,廣度優先搜索類似于樹的層次遍歷，是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優先搜索那樣有回退的情況。因此，廣度優先搜索不是一個遞歸的過程，其算法也不是遞歸的。 為了實現逐層訪問，算法中使用一個隊列，以便于向下一層訪問。 與深度優先搜索過程一樣，為避免重復訪問，需要一個輔助數組visited 。,算法BFS (Head, v, visited. visited) /*廣度優先遍歷算法 */ BFS1初始化 （P142改錯） CREATQ(Q). /*

28、創建隊列 Q */ FOR i = 1 TO n DO visitedi 0. PRINT(v) . visitedv 1. Qv. /* 入隊 */ BFS2廣度優先遍歷 WHILE NOT(ISEMTQ(Q) DO /* 當隊列不空時 */ ( v Q. /* 出隊 */ p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN ( Q VerAdj(p) . PRINT(VerAdj(p) ) . visitedVerAdj(p) 1. ) . p link(p). ) ) ,WHILE NOT(ISEMTQ(Q) DO

29、/* 當隊列不空時 */ ( v Q. /* 出隊 */ p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN ( Q VerAdj(p) . PRINT(VerAdj(p) ) . visitedVerAdj(p) 1. ) p link(p). ) ),算法分析,如果使用鄰接表表示圖，則循環的總時間代價為 d0 + d1 + + dn-1 = O(e)，其中的 di 是頂點 i 的度。總的時間復雜度為O(n+e)。 如果使用鄰接矩陣，則對于每一個被訪問的頂點，循環要檢測矩陣中的 n 個元素，總的時間代價為O(n2)。,第

30、五章 圖 5.1 基本概念 5.2 圖的存儲結構 5.3 圖的遍歷 5.4 拓撲排序 5.5 關鍵路徑 5.6 最短路徑 5.7 最小支撐樹,5.4 拓撲排序 計劃、施工過程、生產流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。 AOV網:在有向圖中，用頂點表示活動，用有向邊表示活動之間的先后關系，稱這樣的有向圖為AOV網(Activity On Vertex Network)。,例如，計算機專業學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程

31、之間有領先關系，有的課程可以并行地學習。,例按拓撲次序安排計算機專業必修課程,在AOV網絡中，如果活動Vi 必須在活動Vj 之前進行，則存在有向邊， AOV網絡中不能出現有向回路，即有向環。在AOV網絡中如果出現了有向環，則意味著某項活動應以自己作為先決條件。 因此，對給定的AOV網絡，必須先判斷它是否存在有向環。,拓撲序列：把AOV網中的所有頂點排成一個線性序列，使每個活動的所有前驅活動都排在該活動的前邊。 拓撲排序：構造AOV網的拓撲序列的過程被稱為拓撲排序。,拓撲序列：C0 , C1 , C2 , C4 , C3 , C5 , C7 , C8 , C6, 拓撲排序基本步驟： 從網中選擇一

32、個入度為0的頂點且輸出之。 從網中刪除該頂點及其所有出邊。 執行 ，直至所有頂點已輸出，或網中剩余頂點入度均不為0 (說明網中存在回路，無法繼續拓撲排序),回路與拓撲排序 任何無回路的AOV網，其頂點均可排成拓撲序列(其拓撲序列不一定唯一)； 如果能將AOV網的所有頂點都排入一個拓撲序列，則該AOV網中必定無有向環；若在有回路的AOV網中，找不到所有頂點的拓撲序列(AOV網所代表的工程是不可行的)。 。 因此，可以用拓撲排序判斷有向圖中是否有回路,假定AOV網用鄰接表的形式存儲。為實現拓撲排序算法，事先需好兩項準備工作： 建立一個數組count ，counti的元素值取對應頂點i的入度； 建立

33、一個堆棧，棧中存放入度為0的頂點，每當一個頂點的入度為0，就將其壓入棧。,拓撲排序算法,用一個堆棧存放入度為 0 的頂點。 虛擬的堆棧利用變量top和count數組元素的值來模擬堆棧的壓入和彈出。 top:“棧頂”位置，初始為-1 counttop：次棧頂元素 入棧：counti = top; top = i; 出棧：j = top; top = counttop;,算法TopoOrder(n) /* 圖的拓撲排序算法 */ TOrder1初始化 /* 計算count數組 */ FOR i = 0 TO n-1 DO counti 0. FOR i = 0 TO n-1 DO ( p adja

34、cent( Headi ) . WHILE p DO (countVerAdj(p) countVerAdj(p)+1. p link (p). ) )/統計每個頂點的入度,拓撲排序算法：/算法TOrder1初始化第二部分 top -1./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點入棧 IF counti = 0 THEN ( counti top. top i. ),拓撲排序算法： /算法TOrder1初始化第二部分 top -1./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點入棧 IF counti = 0 THEN ( count

35、i top. top i. ),TOrder2拓撲排序 FOR i = 1 TO n DO IF top = - 1 THEN / 若循環體尚未被執行n次，棧頂指針已為-1 (PRINT “有回路! ”. RETURN. ) /說明有回路，終止程序 ELSE ( j top. top counttop . /* 彈出棧頂j */ PRINT ( j ) . p adjacent( Headj ) . / 掃描j的邊鏈表 WHILE p DO ( k VerAdj(p) . countk countk-1. / 頂點k的入度減1 IF countk = 0 THEN /若入度為0，則k入棧 (c

36、ountk top. top k.) p link (p). ) ) ,FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top count

37、top . /* 彈出堆棧頂點j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO /* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0， 則k 入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/*

38、 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF

39、countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n DO (j top. top counttop . /* 彈出堆棧頂點j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),FOR i = 1 TO n D

40、O (j top. top counttop . /* 彈出堆棧頂點j */ PRINT ( j ) . p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ),引理5.1 設圖G = (V, E)是非循環圖, V(G), 則G中一定存在入度為零的頂點 定理5.2 設G=(V, E)是非循環圖，V(G)=1, 2 , n, e=|E(

41、G)|. 則算法TopoOrder是正確的且算法的時間復雜性為 O(n+e).,第五章 圖 5.1 基本概念 5.2 圖的存儲結構 5.3 圖的遍歷 5.4 拓撲排序 5.5 關鍵路徑 5.6 最短路徑 5.7 最小支撐樹,5.5 關鍵路徑 5.5.1 基本概念 邊表示活動(Activity) 邊的權值表示活動的持續時間(Duration) 頂點表示入邊的活動已完成，出邊的活動可以開始的狀態，也稱為事件(Event) 這樣的有向無環的帶權圖叫做AOE (Activity On Edges Network)網。,例 某工程 源點：表示整個工程的開始（入度為零）。 匯點：表示整個工程的結束（出度為

42、零）。 完成整個工程至少需要多少時間？ 為縮短工程的時間，應當加快哪些活動？,從源點到各頂點的路徑可能不止一條，路徑長度也可能不同。只有各條路徑上所有活動都完成了，整個工程才算完成。 關鍵路徑：從源點到匯點具有最大長度的路徑稱為關鍵路徑。 路徑長度：指路徑上的各邊權值之和。 關鍵活動：關鍵路徑上的活動。, 關鍵活動有關的量： 事件vi的最早發生時間ve(i): 從源點v0到vi的最長路徑長度。 事件vi的最遲發生時間vl(i): 保證匯點的最早發生時間不推遲的前提下，事件vi允許的最遲開始時間，等于ve(n-1)減去從vi到vn-1最長路徑長度。, 關鍵活動有關的量： 活動ak的最早開始時間e

43、(k): 設活動ak在有向邊上, e(k)是從源 點v0到vi的最長路徑長度。因此e(k)=ve(i)。, 關鍵活動有關的量： 活動ak的最遲開始時間l(k): l(k)是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。 設活動ak在有向邊上,則 l(k)= vl(j)-dur()。, 關鍵活動： l(k) e(k),5.5.2 關鍵活動算法 求關鍵活動的基本步驟： 對AOE網進行拓撲排序，按拓撲次序求出各頂點事件的最早發生時間ve，若網中有回路，則終止算法； 按拓撲序列的逆序求出各頂點事件的最遲發生時間vl 根據ve和vl的值，求出各活動的最早開始時間e(k)與最遲開始時間l(k)，若

44、e(k)= l(k)，則是關鍵活動。,例 求關鍵活動第1步,按拓撲正序遞推: 注：此時j為前驅結點，i為后繼結點,ve(0)=0 ve(1)= ve(0)+weight()=0+6=6 ve(2)= ve(0)+weight()=0+4=4 ve(3)= ve(0)+weight()=0+5=5 ve(4)= maxve(1)+ weight()， ve(2)+ weight() =max6+1,4+1=7,ve(5)= ve(3)+weight()=5+2=7 ve(6)= ve(4)+weight()=7+9=16 ve(7)= maxve(4)+ weight()， ve(5)+ weight()=max7+7,7+4=14 ve(8)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,14+4=18,例 求關鍵活動第2步,按拓撲逆序遞推:,vl(8)= ve(8)=18 vl(7)= vl(8)-weight()=18