1、第七章 圖,圖（Graph）是一種較線性表和樹更為復雜的非線性結構。在線性結構中，結點之間的關系是線性關系，除開始結點和終端結點外，每個結點只有一個直接前趨和直接后繼。在樹形結構中，結點之間的關系實質上是層次關系，同層上的每個結點可以和下一層的零個或多個結點（即孩子）相關，但只能和上一層的一個結點（即雙親）相關（根結點除外）。然而在圖結構中，對結點（圖中常稱為頂點）的前趨和后繼個數都是不加限制的，即結點之間的關系是任意的。圖中任意兩個結點之間都可能相關。由此，圖的應用極為廣泛，特別是近年來的迅速發展，已滲透到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數學的其它分支中。,7.1 圖

2、的定義和術語 圖(Graph)圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對或有序對 有向圖有向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是有向邊（也稱弧）的有限集合，弧是頂點的有序對，記為，v,w是頂點，v為弧尾，w為弧頭,V(G1)= 1, 2, 3, 4, 5, 6 E(G1)=, , , , , , ,無向圖無向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對，記為（v,w）或（w,v)，

3、并且（v,w)=(w,v),V(G2)= 1, 2, 3, 4, 5, 6, 7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),有向完備圖n個頂點的有向圖最大邊數是n(n-1) 無向完備圖n個頂點的無向圖最大邊數是n(n-1)/2 權與圖的邊或弧相關的數叫 網帶權的圖叫 子圖如果圖G(V, E)和圖G(V,E),滿足： V V E E 則稱G為G的子圖 頂點的度 無向圖中，頂點的度為與每個頂點相連的邊數 有向圖中，頂點的度分成入度與出度 入度：以該頂點為頭的弧的數目 出度：以該頂點為尾的弧的數目 路徑路徑是頂點的序列V=Vi0,Vi1

4、,Vin，滿足(Vij-1,Vij)E 或 E,(1jn),路徑長度沿路徑邊的數目或沿路徑各邊權值之和 回路第一個頂點和最后一個頂點相同的路徑叫 簡單路徑序列中頂點不重復出現的路徑叫 簡單回路除了第一個頂點和最后一個頂點外，其余頂點不重復出現的回路叫 連通從頂點V到頂點W有一條路徑，則說V和W是 連通圖圖中任意兩個頂點都是連通的叫 連通分量非連通圖的每一個連通部分叫 強連通圖有向圖中，如果對每一對Vi,VjV, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑，則稱G是,路徑：1，2，3，5，6，3 路徑長度：5 簡單路徑：1，2，3，5 回路：1，2，3，5，6，3，1 簡單回路：3，5，

5、6，3,路徑：1，2，5，7，6，5，2，3 路徑長度：7 簡單路徑：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 簡單回路：1，2，3，1,連通圖,強連通圖,非連通圖 連通分量,若將圖的每條邊都賦上一個權，則稱這種帶權圖為網絡(Network)。 通常權是具有某種意義的數，它們可以表示兩個頂點之間的距離，耗費等。,圖的存儲表示分析 特點：頂點之間的關系是多對多(m : n)m 和 n 都是不定的，無法進行非線性結構的線性化圖中的關系不能通過順序映像(即通過頂點之間的存儲位置反映頂點之間的邏輯關系)反映；必須另外引入存儲空間反映頂點之間的鄰接關系。 圖的存儲信息頂點信息、邊/弧信息

6、、整體信息：頂點數、邊/弧數、圖的種類(有向圖/有向網/無向圖/無向網) 頂點集：順序表存儲，不是順序映像！ 關系集：鄰接矩陣、鄰接表、多重鄰接表、十字鏈表,7.2 存儲結構,（1）圖的鄰接矩陣表示法,鄰接矩陣表示頂點間相聯關系的矩陣 定義：設G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A是具有以下性質的n階方陣,圖：鄰接關系用1/0表示 網：鄰接關系需要進一步反映權值，用INFINITY表示無窮大，反映頂點之間無鄰接關系 #defineINT_MAX32767/* 最大整數*/ #defineINFINITYINT_MAX,1) 鄰接矩陣 typedef struct ArcCell in

7、tadj;/ 頂點間關系，無權圖：0-不相鄰，1-相鄰 / 有權圖，權值，INFINITY-不相鄰 InfoType*info;/ 該弧相關信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,2) 圖的整體結構 typedef struct VertexTypevexsMAX_VERTEX_NUM; /* 有效的頂點下標從0開始 */ AdjMatrixarcs;/* 關系集 */ intvexnum, arcnum; /* 頂點數、邊/弧數 */ GraphKindkind;/* 圖的種類*/ MGraph;,V1,V3,V2,V4,V

8、1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0,V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0,圖的連接矩陣表示法,特點： 無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2 有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為n 無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和 有向圖中， 頂點Vi的出度是A中第i行元素之和 頂點Vi的入度是A中第i列元素之和 網絡的鄰接矩陣可定義為：,V1 V2 V3 V4 V1 0 0

9、 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0,V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0,入度 出度,1 1,1 1,2 1,0 1,度數,3,2,1,2,（2）圖的鄰接表示法 即對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于該頂點Vi的邊（或弧）。,圖的整體結構 typedef struct AdjListvertices; intvexnum, arcnum; GraphKindkind; ALGraph;,特點 無向圖中頂點Vi的度為第i個單鏈表中的結點數 有向圖中 頂點Vi的

10、出度為第i個單鏈表中的結點個數 頂點Vi的入度為整個單鏈表中鄰接點域值是i的結點個數 逆鄰接表：有向圖中對每個結點建立以Vi為頭的弧的單鏈表,7.3 圖的遍歷 和樹的遍歷類似，圖的遍歷也是從某個頂點出發，沿著某條搜索路徑對圖中所有頂點各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點出發順著邊可以訪問到該圖的所有頂點。然而，圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一頂點都可能和其余頂點相鄰接，故在訪問了某個頂點之后，可能順著某條回路又回到了該頂點。為了避免重復訪問同一個頂點，必須記住每個頂點是否被訪問過。,1、深度優先遍歷(DFS) 方法：從圖的某一頂點V0出發，訪問此頂點；然后依次從V0

11、的未被訪問的鄰接點出發，深度優先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7,深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5,深度優先遍歷算法 遞歸算法,Firstadj(G,v)返回圖G中頂點v的第一個鄰接點的編號，若不存在，則返回0； Nextadj(G,v,w)返回圖G中頂點v的鄰接點中處于w之后

12、的那個鄰接點的編號，若不存在，則返回0； 約定：搜索鄰接點將按從小到大的次序進行。,void traver(TD g) int i; static int visitedM; for(i=1;i=n;i+) visitedi= FALSE; / 訪問標志數組初始化 for(i=1;i=n;i+) if(!visitedi) dfs(i); ,void dfs(int v0) / 從頂點v0出發，深度優先搜索遍歷連通圖 G printf(“%d ”, v0); visitedv0=true; /訪問頂點v0 w=firstadjG, v0; /返回v0的第一個鄰接點 while(w!=0) if

13、(!visitedw) dfs(w); /從v0的鄰接點出發做深度遍歷 w=nextadj(G, v0, w); /取下一個鄰接點 ,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,基于某種存儲結構的DFS算法 根據選擇的存儲結構，決定 FirstAdjVex()和NextAdjVex()的實現，重新整合算法。 如采用鄰接矩陣表示法表示的圖，則DFS算法如下： void DFS (MGraph G, int v, Status ( *Visit ) (MGraph G, int v) visitedv

14、= TRUE; Visit(G, v); for ( w = 0; w G.vexnum; w +) if ( G.arcsvw.adj ,采用鄰接表表示法表示的圖，則DFS算法如下： void DFS (ALGraph G, int v, Status ( *Visit ) (ALGraph G, int v) ) visitedv = TRUE; Visit(G, v); for ( p = G.verticesv.firstarc; p ; p = p-nextarc) if (!visitedp-adjvex )DFS(G, p-adjvex, Visit); ,應用：圖的深度優先遍歷

15、： 1、 求一條包含圖中所有頂點的簡單路徑(簡單回路) 2、 判斷圖中是否存在環 3、 求圖中通過給定頂點vk的簡單回路 4、 判斷是否存在從頂點vi到頂點vj的路徑 5、 判別v0和v1之間是否存在一條長度為k的路徑,求一條包含圖中所有頂點的簡單路徑,1、思路 對于任意的有向圖或無向圖G，并不一定都能找到符合題意的簡單路徑。這樣的簡單路徑要求包含G.vexnum個頂點，且互不相同。它的查找可以基于深度優先遍歷。,在一個存在包含全部頂點的簡單路徑的圖中，以下因素會影響該簡單路徑是否能順利地查到： 1） 起點的選擇：如圖(a)，其符合題意的一條簡單路徑如圖(b)。若起點為1，則不能找到符合題意的

16、簡單路徑； 2）頂點的鄰接點次序：進一步考察圖(a)，即使以2為起點，但是2的鄰接點選擇的是1，而不是5，此時也不能找到符合題意的解。,在基于DFS的查找算法中，由于起點和鄰接點的選取是與頂點和鄰接點的存儲次序以及算法的搜索次序有關，不可能依據特定的圖給出特定的解決算法。因此，在整個搜索中應允許有查找失敗，此時可采取回溯到上一層的方法，繼續查找其他路徑。 這樣，引入數組Path用來保存當前已搜索的簡單路徑上的頂點，引入計數器n用來記錄當前該路徑上的頂點數。,對DFS算法的修改如下： 1） 計數器n的初始化，放在visited的初始化前后； 2） 訪問頂點時，增加將該頂點序號入數組Path中，計

17、數器n+；判斷是否已獲得所求路徑，是則輸出結束，否則繼續遍歷鄰接點； 3） 某頂點的全部鄰接點都訪問后，仍未得到簡單路徑，則回溯，將該頂點置為未訪問，計數器n-。,1）,1、算法 /* 鄰接矩陣表示法*/ voidHamilton(MGraph G) for ( i=0; iG.vexnum; i+ ) visitedi = FALSE; n = 0; for ( i=0; iG.vexnum; i+ ) if ( !visitedi ) DFS (G, i); voidDFS(MGraph G, int i) visitedi = TRUE; Pathn = i; n+; if ( n =

18、G.vexnum )Print(Path);/* 符合條件，輸出該簡單路徑*/ for( j=0; jG.vexnum; j+ ) if ( G.arcsij.adj ,2、廣度優先遍歷(BFS) 方法：從圖的某一頂點V0出發，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發，廣度優先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍

19、歷：V1 V2 V3 V4 V6 V7 V8 V5,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,算法思路： （1）訪問V0 （2）依次訪問V0 的所有鄰接點v11,v12, ,v1k （3）設剛剛被訪問過的一層頂點依次為vi1,vi2, ,vik 則依次訪問vi1,vi2, ,vik的未被訪問的鄰接點 （4）重復（3）,廣度優先遍歷算法,void traver(graph G) int i; static int visitedM; for(i=1;i=n;i+) visitedi=false; for(i=1;i=n;i+) if(!visitedi) bfs(i); ,voi

20、d bfs(graph G,int v0) printf(“%dn”,v); visitedv0=true; /訪問頂點v0，置訪問隊列 Q.enqueue(v0); /v0 入隊 while(!Q.empty( ) /隊列Q不空時 v=Q.delqueue( ); /取隊頭 w=firstadj(G,v); /取v第一個鄰接點 while(w!=0) if (! Visitedw) printf(%dn,w); visitedw=true; Q.enqueue(w); /訪問W入隊，置訪問標志 w=nextadj(G,v,w); /求下一個鄰接點 ,應用：圖的廣度優先遍歷： 1、 判斷是否存

21、在從頂點vi到頂點vj的路徑 2、 求距v0的各頂點中最短路徑長度最長的一個頂點。 3、 求v0和v1之間的最短路徑. 4、 在頂點子集U中找出距離頂點v0最近的頂點 5、 求頂點v0到其余每個頂點的最短路徑 6、 求距離頂點v0的最短路徑長度為k的所有頂點,求距v0的各頂點中最短路徑長度最長的一個頂點,1、思路 由于題意強調為最短路徑，因此應當考慮BFS的算法應用。本問題的求解轉變成：從v0出發進行BFS，最后一層的頂點距離v0的最短路徑長度最長。 由于BFS類似于樹的按層次遍歷，需要引入隊列用來保存本身已訪問但其鄰接點尚未全部訪問的頂點。BFS遍歷中最后一層的頂點一定是最后出隊的若干頂點，

22、隊列中最后一個出隊的頂點必定是符合題意的頂點。 這樣，只需調用BFS的算法，將最后出隊的元素返回即可。,2、算法 int MaxDistance (MGraph G, int v0 ) /* 初始化各頂點的訪問標志，設置為未訪問*/ for ( i=0; iG.vexnum; i+ ) visitedi = FALSE; InitQueue(Q); /* 不需要考慮其他的連通分量，因為所求的頂點必定與v0在同一個連通分量中 */ EnQueue (Q, v0 ); visitedv0 = TRUE; while( !QueueEmpty(Q) ) DeQueue(Q, v); for( w=0

23、; wG.vexnum; w+ ) if ( G.arcsvw.adj ,7.4 最小生成樹 圖的生成樹不是唯一的，從不同的頂點出發進行遍歷，可以得到不同的生成樹。對于連通網絡G(V，E)，邊是帶權的，因而G的生成樹的各邊也是帶權的。我們把生成樹各邊的權值總和稱為生成樹的權，并把權最小的生成樹稱為G的最小生成樹(Minimum Spanning Tree)。 生成樹和最小生成樹有許多重要的應用。令圖G的頂點表示城市，邊表示連接兩個城市之間的通訊線路。n個城市之間最多可設立的線路有n(n-1)2條，把n個城市連接起來至少要有n-1條線路，則圖G的生成樹表示了建立通訊網絡的可行方案。如果給圖中的邊

24、都賦予權，而這些權可表示兩個城市之間通訊線路的長度或建造代價，那么，如何選擇n-1條線路，使得建立的通訊網絡其線路的總長度最短或總代價最小呢?這就是要構造該圖的一棵最小生成樹。,生成樹 定義：所有頂點均由邊連接在一起，但不存在回路的圖叫 深度優先生成樹與廣度優先生成樹 生成森林：非連通圖每個連通分量的生成樹一起組成非連通圖的 說明 一個圖可以有許多棵不同的生成樹 所有生成樹具有以下共同特點： 生成樹的頂點個數與圖的頂點個數相同 生成樹是圖的極小連通子圖 一個有n個頂點的連通圖的生成樹有n-1條邊 生成樹中任意兩個頂點間的路徑是唯一的 在生成樹中再加一條邊必然形成回路 含n個頂點n-1條邊的圖不

25、一定是生成樹,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,最小生成樹 問題提出,要在n個城市間建立通信聯絡網， 頂點表示城市， 權城市間建立通信線路所需花費代價， 希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網所需花費的總代價）最小最小代價生成樹。,問題分析,n個城市間，最多可設置n(n-1)/2條線路， n個城市間建立通信網，只需n-1條線路， 問題轉化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費（各邊權值之和）最小。,構造最小生成樹方法 方法一：普里姆(Prim)算法 算法思想

26、：設N=(V,E)是連通網，TE是N上最小生成樹中邊的集合 初始令U=u0,(u0V), TE= 在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0) 將(u0,v0)并入集合TE，同時v0并入U 重復上述操作直至U=V為止，則T=(V,TE)為N的最小生成樹 算法實現：圖用鄰接矩陣表示 算法描述 算法評價：T(n)=O(n),#define M 30 #define MAX 100 void minispantree_PRIM(int adM,int n) int i,j,k,p,q,wm; q=p=n-1; adqq=1; for(k=0;kq) adpq=-adpq;

27、 else adqp=-adqp; ,1,1,1,-2,1,-4,1,-1,1,-5,1,-3,方法二：克魯斯卡爾(Kruskal)算法 算法思想：設連通網N=(V,E)，令最小生成樹 初始狀態為只有n個頂點而無邊的非連通圖T=(V,)，每個頂點自成一個連通分量 在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊 依此類推，直至T中所有頂點都在同一連通分量上為止,（0）用頂點數組和邊數組存放頂點和邊信息 （1）初始時，令每個頂點的jihe互不相同；每個邊的flag為0 （2）選出權值最小且flag為0的邊 （3）若該邊依

28、附的兩個頂點的jihe 值不同，即非連通，則令該邊的flag=1, 選中該邊；再令該邊依附的兩頂點的jihe以及兩集合中所有頂點的jihe 相同若該邊依附的兩個頂點的jihe 值相同，即連通，則令該邊的flag=2, 即舍去該邊。 （4）重復上述步驟，直到選出n-1條邊為止。,頂點結點： typedef struct int data; /頂點信息 int jihe; VEX;,邊結點： typedef struct int vexh, vext; /邊依附的兩頂點 int weight; /邊的權值 int flag; /標志域 EDGE;,算法實現：,算法描述：,1,1,1,1,1,4,2

29、,1,1,1,2,2,2,2,2,void minitree_KRUSKAL(void) int n,i,m,min,k,j; VEX tM; EDGE eM; printf(Input number of vertex and edge:); scanf(%d,%d, ,i=1; while(in) min=MAX; for(j=0;jm;j+) if(ej.weightmin ,7.5 有向無環圖及應用,通常我們把計劃、施工過程、生產流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動，這些活動完成時，整個工程也就完成了。例如，計算機專業學生的課程開

30、設可看成是一個工程，每一門課程就是工程中的活動，下圖給出了若干門所開設的課程，其中有些課程的開設有先后關系，有些則沒有先后關系，有先后關系的課程必須按先后關系開設，如開設數據結構課程之前必須先學完程序設計基礎及離散數學，而開設離散數學則必須學完高等數學。我們用一種有向圖來表示課程開設，在這種有向圖中，頂點表示活動，有向邊表示活動的優先關系，這有向圖叫做頂點表示活動的網絡(Activity On Vertex)簡稱為AOV網。,一、AOV網及拓撲排序 問題提出：學生選修課程問題 頂點表示課程 有向弧表示先決條件，若課程i是課程j的先決條件， 則圖中有弧 學生應按怎樣的順序學習這些課程，才能無矛盾

31、、順利地完成學業拓撲排序,定義 AOV網用頂點表示活動，用弧表示活動間優先關系的有向圖稱為頂點表示活動的網(Activity On Vertex network)，簡稱AOV網。 若是圖中有向邊，則vi是vj的直接前驅；vj是vi的直接后繼 AOV網中不允許有回路，這意味著某項活動以自己為先決條件 拓撲排序把AOV網絡中各頂點按照它們相互之間的優先關系排列成一個線性序列的過程叫。 檢測AOV網中是否存在環方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都在它的拓撲有序序列中，則該AOV網必定不存在環,拓撲排序的方法 在有向圖中選一個沒有前驅的頂點且輸出之 從圖中刪除該頂點和所有以它為尾的

32、弧 重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止。,拓撲序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一個AOV網的拓撲序列不是唯一的,算法實現 以鄰接表作存儲結構 把鄰接表中所有入度為0的頂點進棧 棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧 重復上述操作直至棧空為止。若棧空時輸出的頂點個數不是n，則有向圖有環；否則，拓撲排序完畢。,鄰接表結點： typedef struct node

33、 int vex; /頂點域 struct node *next; /鏈域 JD;,表頭結點： typedef struct tnode int in; /入度域 struct node *link; /鏈域 TD; TD gM; /g0不用,算法描述,1,6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6 1,輸出序列：6 1,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1 3,

34、4,3,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3 2,4,2,輸出序列：6 1 3 2,4,輸出序列：6 1 3 2 4,4,輸出序列：6 1 3 2 4,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4 5,5,輸出序列：6 1 3 2 4 5,算法分析,建鄰接表：T(n)=O(e) 搜索入度為0的頂點的時間：T(n)=O(n) 拓撲排序：T(n)=O(n+e),void toposort(TD g

35、,int n) int top,m,k,j; JD *p; top=0; m=0; for(j=1;j0) j=top; top=gtop.in; printf(%dn,j); m+; p=gj.link; while(p!=NULL) k=p-vex; gk.in-; if(gk.in=0) gk.in=top; top=k; p=p-next; printf(m=%dn,m); if(mn) printf(The network has a cyclen); ,二、關鍵路徑 問題提出,把工程計劃表示為有向圖，用頂點表示事件，弧表示活動； 每個事件表示在它之前的活動已完成，在它之后的活動可以

36、開始,例 設一個工程有11項活動，9個事件 事件 V1表示整個工程開始 事件V9表示整個工程結束 問題：（1）完成整項工程至少需要多少時間？ （2）哪些活動是影響工程進度的關鍵？,定義 AOE網(Activity On Edge)也叫邊表示活動的網。AOE網是一個帶權的有向無環圖，其中頂點表示事件，弧表示活動，權表示活動持續時間 路徑長度路徑上各活動持續時間之和 關鍵路徑路徑長度最長的路徑叫 Ve(j)表示事件Vj的最早發生時間 Vl(j)表示事件Vj的最遲發生時間 e(i)表示活動ai的最早開始時間 l(i)表示活動ai的最遲開始時間 l(i)-e(i)表示完成活動ai的時間余量 關鍵活動關

37、鍵路徑上的活動叫，即l(i)=e(i)的活動,問題分析 如何找e(i)=l(i)的關鍵活動？,設活動ai用弧表示，其持續時間記為：dut() 則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,(1)從Ve(1)=0開始向前遞推,(2)從Vl(n)=Ve(n)開始向后遞推,求關鍵路徑步驟 求Ve(i) 求Vl(j) 求e(i) 求l(i) 計算l(i)-e(i),V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7

38、 a8 a9 a10 a11, ,算法實現 以鄰接表作存儲結構 從源點V1出發，令Ve1=0,按拓撲序列求各頂點的Vei 從匯點Vn出發，令Vln=Ven,按逆拓撲序列求其余各頂點的Vli 根據各頂點的Ve和Vl值，計算每條弧的ei和li,找出ei=li的關鍵活動,鄰接表結點： typedef struct node int vex; /頂點域 int length; struct node *next; /鏈域 JD;,表頭結點： typedef struct tnode int vexdata; int in; /入度域 struct node *link; /鏈域 TD; TD gM;

39、/g0不用,算法描述 輸入頂點和弧信息，建立其鄰接表 計算每個頂點的入度 對其進行拓撲排序 排序過程中求頂點的Vei 將得到的拓撲序列進棧 按逆拓撲序列求頂點的Vli 計算每條弧的ei和li,找出ei=li的關鍵活動,問題提出,用帶權的有向圖表示一個交通運輸網，圖中： 頂點表示城市 邊表示城市間的交通聯系 權表示此線路的長度或沿此線路運輸所花的時間或費用等 問題：從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中， 各邊上權值之和最小的一條路徑最短路徑,7.6 最短路徑,1、從某個源點到其余各頂點的最短路徑,13,8,13,19,21,20,迪杰斯特拉(Dijkstra)算法思想,按路徑長度遞增

40、次序產生最短路徑算法： 把V分成兩組： （1）S：已求出最短路徑的頂點的集合 （2）V-S=T：尚未確定最短路徑的頂點集合 將T中頂點按最短路徑遞增的次序加入到S中， 保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于 從V0到T中任何頂點的最短路徑長度 （2）每個頂點對應一個距離值 S中頂點：從V0到此頂點的最短路徑長度 T中頂點：從V0到此頂點的只包括S中頂點作中間 頂點的最短路徑長度,依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的 直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和 （反證法可證）,求最短路徑步驟 初使時令 S=V0,T=其余頂點，T中頂點對應

41、的距離值 若存在，為弧上的權值 若不存在，為 從T中選取一個其距離值為最小的頂點W，加入S 對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值 重復上述步驟，直到S中包含所有頂點，即S=V為止,13 8 30 32 V2:8 ,13 - 13 30 32 V1:13 ,- - 13 30 22 20 V3:13 ,- - - 19 22 20 V4:19 ,- - - - 21 20 V6:20 ,算法實現 圖用帶權鄰接矩陣存儲ad 數組dist存放當前找到的從源點V0到每個終點的最短路徑長度，其初態為圖中直接路徑權值 數組pre表示從V0到

42、各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號,算法描述,1,13,3,1,22,20,2,2,19,4,1,21,5,1,1,1,13,8,13,19,21,20,算法分析：T(n)=O(n),void shortpath_DIJ(int adM,int k,int pre, int dist,int n) int i,j,p,wm; k=k-1; for(i=0;in;i+) disti=adki; if(distiMAX) prei=k+1; else prei=0; prek=0; distk=0; adkk=1; for(j=0;j(n

43、-1);j+) wm=MAX; p=-1; for(i=0;in;i+) if(adii=0) ,2、每一對頂點之間的最短路徑 方法一：每次以一個頂點為源點，重復執行Dijkstra算法n次 T(n)=O(n) 方法二：弗洛伊德(Floyd)算法 算法思想：逐個頂點試探法 求最短路徑步驟 初始時設置一個n階方陣，令其對角線元素為0，若存在弧，則對應元素為權值；否則為 逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值 所有頂點試探完畢，算法結束,算法實現 圖用鄰接矩陣存儲 length存放最短路徑長度 pathij是從Vi到Vj的最短路徑上Vj前一頂點序號 算法描述,算法分析：T(n)=O(n),void shortpath_FLOYD(int costM,int pathM,int lengthM,int n) int i,j,k,wm; for(i=0;in;i+) for(j=0;jn;j+) lengthij=costij; if(i=j) pathij=0; else if(lengthijMAX) pathij=i+1; else pathij=0; for(k=0;kn;k+) fo