1、7.1 圖的定義和術語7.2 圖的存儲表示7.3 圖的遍歷7.4 圖的連通性問題(最小生成樹)7.5 兩點之間的最短路徑問題7.6 拓撲排序7.7 關鍵路徑第7章 圖 圖是由一個頂點集 V 和一個弧集 R構成的數據結構。 Graph = (V , R )其中，R| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 v 為弧頭，w 為弧尾。 圖的定義:VW7.1 圖的定義和術語 由于“弧”是有方向的，因此稱由頂點集和弧集構成的圖為有向圖。 AB E C D例如:G1 = (V1, VR1)其中:V1=A, B, C, D, EVR1=, , , , , , 若VR 必有VR, 則稱

2、 (v,w) 為頂點v 和頂點 w 之間存在一條邊。 B CA D F E由頂點集和邊集構成的圖稱作無向圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A,B), (A,E), (B,E), (C,D), (D,F), (B,F), (C,F) 名詞和術語網、子圖 完全圖、稀疏圖、稠密圖鄰接點、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強連通圖、強連通分量生成樹、生成森林ABECFAEABBC設圖G=(V,VR) 和圖 G=(V,VR),且 VV, VRVR,則稱 G 為 G 的子圖。1597211132 弧或邊帶權的圖分別稱作有向網或

3、無向網。假設圖中有 n 個頂點，e 條邊，則 含有 e=n(n-1)/2 條邊的無向圖稱作完全圖； 含有 e=n(n-1) 條弧的有向圖稱作 有向完全圖； 若邊或弧的個數 enlogn，則稱作稀疏圖，否則稱作稠密圖。 假若頂點v 和頂點w 之間存在一條邊，則稱頂點v 和w 互為鄰接點，ACDFE例如:ID(B) = 3ID(A) = 2 邊(v,w) 和頂點v 和w 相關聯。 和頂點v 關聯的邊的數目定義為頂點v的度。B頂點的出度: 以頂點v為弧尾的弧的數目；ABECF對有向圖來說，頂點的入度: 以頂點v為弧頭的弧的數目。頂點的度(TD)=出度(OD)+入度(ID)例如:ID(B) = 2OD

4、(B) = 1TD(B) = 3設圖G=(V,VR)中的一個頂點序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點u 到頂點w 之間存在一條路徑。路徑上邊的數目稱作路徑長度。ABECF如:長度為3的路徑A,B,C,F簡單路徑:序列中頂點不重復出現的路徑。簡單回路:序列中第一個頂點和最后一個頂點相同的簡單路徑。回路或環:序列中第一個頂點和最后一個頂點相同的路徑。若圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖；若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE 若任意兩個頂點之間都存在一條有向路徑，則稱

5、此有向圖為強連通圖。ABECFABECF對有向圖， 否則，其各個強連通子圖稱作它的強連通分量。 假設一個連通圖有 n 個頂點和 e 條邊，其中 n-1 條邊和 n 個頂點構成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。BACDFE若在一棵生成樹上添加一條邊必構成一個環若n個頂點無向連通圖有大于n-1條邊,則一定有環,但有n-1條邊的圖不一定是生成樹或連通圖BACDFEBACDFE結構的建立和銷毀插入或刪除頂點對鄰接點的操作對頂點的訪問操作遍歷插入和刪除弧基本操作CreatGraph(&G, V, VR): / 按定義

6、(V, VR) 構造圖DestroyGraph(&G): / 銷毀圖結構的建立和銷毀對頂點的訪問操作LocateVex(G, u); / 若G中存在頂點u，則返回該頂點在 / 圖中“位置” ；否則返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 對 v 賦值value。對鄰接點的操作 FirstAdjVex(G, v); / 返回 v 的“第一個鄰接點” 。若該頂點/在 G 中沒有鄰接點，則返回“空”。 NextAdjVex(G, v, w); / 返回 v 的（相對于 w 的） “下一個鄰接/ 點”。若 w 是 v 的最后一個鄰接點

7、，則/ 返回“空”。插入或刪除頂點InsertVex(&G, v); /在圖G中增添新頂點v。DeleteVex(&G, v); / 刪除G中頂點v及其相關的弧。插入和刪除弧InsertArc(&G, v, w); / 在G中增添弧，若G是無向的， /則還增添對稱弧。DeleteArc(&G, v, w); /在G中刪除弧，若G是無向的， /則還刪除對稱弧。遍 歷DFSTraverse(G, v, Visit(); /從頂點v起深度優先遍歷圖G，并對每/個頂點調用函數Visit一次且僅一次。BFSTraverse(G, v, Visit(); /從頂點v起廣度優先遍歷圖G，并對每/個頂點調用函

8、數Visit一次且僅一次。在前述圖的基本操作的定義中,”頂點的位置”和”鄰接點的位置”是一個相對的概念:在邏輯結構中,頂點之間不存在全序關系,任一頂點都可被作為第一個頂點,任一頂點的鄰接點之間也不存在次序關系,但為實現操作,需將頂點按任意順序編號排列(該排列與關系VR無關).在存儲結構中,結構和算法確定鄰接頂點(下一個鄰接點)位置也確定.7.2 圖的存儲表示7.2.1 圖的數組(鄰接矩陣)存儲表示7.2.2 圖的鄰接表存儲表示7.2.3 有向圖的十字鏈表存儲表示 7.2.4 無向圖的鄰接多重表存儲表示Aij=0 (i,j)VR1 (i,j)VR7.2.1 圖的數組(鄰接矩陣)存儲表示BACDF

9、E定義:矩陣的元素為無向圖的鄰接矩陣為對稱矩陣A B C D E FABCDEF有向圖的鄰接矩陣為非對稱矩陣ABDCEA B C D EABCDE鄰接矩陣表示法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點v的度：在無向圖中等于二維數組對應行（或列）中1的個數；在有向圖中, 統計第 i 行 1 的個數可得頂點 i 的出度，統計第 j 列 1 的個數可得頂點 j 的入度。3）判斷兩頂點v、u是否為鄰接點：只需判二維數組對應分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數組對應分量賦值1或清0；5）設存儲頂點的一維數組大小為n(圖的頂點數n), G占用存儲空間：n+n

10、2；G占用存儲空間只與它的頂點數有關，與邊數無關；適用于邊稠密的圖；typedef struct ArcCell / 弧的定義 VRType adj; / VRType是頂點關系類型 / 對無權圖，用1或0表示相鄰否； / 對帶權圖，則為權值類型。 InfoType *info; / 該弧相關信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct / 圖的定義 VertexType / 頂點信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息 int vexnum, arcn

11、um; / 頂點數，弧數 GraphKind kind; / 圖的種類標志 MGraph;網絡的鄰接矩陣ABDCA 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE7.2.2圖的鄰接表 存儲表示 同一個頂點發出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊(邊結點), 結點中有另一頂點的下標 adjvex 和指針 nextedge。1 4230 1201234 A B C D E有向圖的鄰接表ABECD可見，在有向圖的鄰接表中不易找到指向該頂點的弧。ABECD有向圖的逆鄰接表A B C D E 30342001234在

12、有向圖的鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。鄰接表表示法特點：1）無向圖鄰接表邊結點數是邊數的兩倍.2）頂點vi的度：在無向圖中等于第i個鏈表中的結點數；在有向圖鄰接表中,第i行的結點數等于頂點i的出度，在有向圖逆鄰接表中,第i行的結點數等于頂點i的入度。3）在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點4）設存儲頂點的一維數組大小為n(圖的頂點數n), G占用存儲空間：n+e；G占用存儲空間與它的頂點數和邊數有關；適用于邊稀疏的圖；typedef struct ArcNode int adjvex; / 該弧所指向的頂點的位置 struct ArcNode *nextarc

13、; / 指向下一條弧的指針 InfoType *info; / 該弧相關信息的指針 ArcNode;adjvex nextarc info弧的結點結構typedef struct VNode VertexType data; / 頂點信息 ArcNode *firstarc; / 指向第一條依附該頂點的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc頂點的結點結構typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標志 ALGraph;圖的結構定義三、有向圖的十字鏈表

14、存儲表示 弧的結點結構弧尾頂點位置 弧頭頂點位置 弧的相關信息指向下一個有相同弧尾的結點指向下一個有相同弧頭的結點typedef struct ArcBox / 弧的結構表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;頂點的結點結構頂點信息數據 指向該頂點的第一條入弧指向該頂點的第一條出弧typedef struct VexNode / 頂點的結構表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct

15、 VexNode xlistMAX_VERTEX_NUM; / 頂點結點(表頭向量) int vexnum, arcnum; /有向圖的當前頂點數和弧數 OLGraph;有向圖的結構表示(十字鏈表)ABCDABCD010220233031320123四、無向圖的鄰接多重表存儲表示typedef struct Ebox VisitIf mark; / 訪問標記 int ivex, jvex; /該邊依附的兩個頂點的位置 struct EBox *ilink, *jlink; InfoType *info; / 該邊信息指針 EBox;邊的結構表示typedef struct / 鄰接多重表 Ve

16、xBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;頂點的結構表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一條依附該頂點的邊 VexBox;無向圖的結構表示ABCDE01234ABCDE0103212324417.3 圖的遍歷 從圖中某個頂點出發游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。深度優先搜索廣度優先搜索遍歷應用舉例 從圖中某個頂點V0 出發，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發深度優先搜索遍歷圖，直

17、至圖中所有和V0有路徑相通的頂點都被訪問到。一、深度優先搜索遍歷圖連通圖的深度優先搜索遍歷Vw1SG1SG2SG3W1、W2和W3 均為 V 的鄰接點，SG1、SG2 和 SG3 分別為含頂點W1、W2和W3 的子圖。訪問頂點 V ：for (W1、W2、W3 ) 若該鄰接點W未被訪問， 則從它出發進行深度優先搜索遍歷(遞歸調用)。w2w3w2從上頁的圖解可見:1. 從深度優先搜索遍歷連通圖的過程類似于樹的先根遍歷；解決的辦法是：為每個頂點設立一個 “訪問標志 visitedw(一維數組)”。2. 如何判別V的鄰接點是否被訪問？acbdegfF F F F F F F TTTTTTTacbdg

18、fe acbgfed訪問標志:訪問次序:例如:0 1 2 3 4 5 6 0234516void DFS(Graph G, int v) / 從頂點v出發，深度優先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 對v的尚未訪問的鄰接頂點w / 遞歸調用DFS / DFS 首先將圖中每個頂點的訪問標志設為 FALSE, 之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優先搜索遍歷，否則繼續檢

19、查下一頂點。非連通圖的深度優先搜索遍歷abchdekfgF F F F F F F F FTTTTTTTTTachdkfe bgachkfedbg訪問標志:訪問次序:例如:0 1 2 3 4 5 6 7 8021345678void DFSTraverse(Graph G, Status (*Visit)(int v) / 對圖 G 作深度優先遍歷。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標志數組初始化 for (v=0; vw1, V-w2, V-w8 的路徑長度為1；V-w7, V-w3, V-w

20、5 的路徑長度為2；V-w6, V-w4 的路徑長度為3。w1Vw2w7w6w3w8w5w4 從圖中的某個頂點V0出發，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后分別從這些鄰接點出發依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有和V0有路徑相通的頂點都被訪問到。 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4F F F F F F F F FTTTTTTTTT0 1 2 3 4 5 6

21、7 8VisitedQV訪問次序:w1w2w8w4w7w3w5w6 void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化訪問標志 InitQueue(Q); / 置空的輔助隊列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未訪問 / BFSTraverse visitedu = TRUE; Visit(u); / 訪問uEnQueue(Q, v); / v入隊列while (!QueueEmpty(Q)

22、 DeQueue(Q, u); / 隊頭元素出隊并置為u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點w入隊列 / if / while1. 若圖的某存儲結構已確定,且算法程序也確定,從某一頂點遍歷圖,其結果是 否唯一 ? 2. 遍歷能否判斷連通性? 3. 兩種遍歷算法的時間復雜度和空間復雜度?(時間復雜度取決于圖的存儲結構,原操作為找鄰接點的操作) 連通分量 (Connected component) 當無向

23、圖為非連通圖時, 從圖中某一頂點出發, 利用深度優先搜索算法或廣度優先搜索算法不可能遍歷到圖中的所有頂點, 只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。圖的連通性問題LEDHGABFICJKM 若從無向圖的每一個連通分量中的一個頂點出發進行遍歷, 可求得無向圖的所有連通分量。 求連通分量的算法需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發遍歷圖，可求得圖的另一個連通分量。 對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。EDHGIKLABFCJMHGIKLABFCJMED非連通無向圖DFS 訪問

24、序列:ALMJBFC DE GKHILABFCJMHGIKLABFCJMEDEDHGIKHGIKLABFCJMED7.4 (連通網的)最小生成樹 假設要在 n 個城市之間建立通訊聯絡網，則連通 n 個城市只需要修建 n-1條線路，如何在最節省經費的前提下建立這個通訊網？問題： 構造網的一棵最小生成樹，即： 在 e 條帶權的邊中選取 n-1 條邊（不構成回路），使“權值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價于：算法一：（普里姆算法） 假設N=V,E)是連通網，TE是N上最小生成樹邊的集合。算法從Uu0(u0V)，TE= 開始，重復執行下述操作：在所有uV，vV-U的邊(u,v)E中找

25、一條代價最小的邊（ u0，v0）并入集合TE,同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=(V,TE)為N的最小生成樹。普里姆算法的基本思想: 在生成樹的構造過程中，圖中 n 個頂點分屬兩個集合：已落在生成樹上的頂點集 U 和尚未落在生成樹上的頂點集V-U ，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。 一般情況下所添加的頂點應滿足下列條件:abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權值和= 14+8+3+5+16+21 = 67 設置一個輔助數組，對每個頂點，記錄從頂點集U到VU具有代價最小的邊：st

26、ruct VertexType adjvex; / U集中的頂點 VRType lowcost; / 邊的權值 closedgeMAX_VERTEX_NUM; adjvex lowcostabcdegf195141827168213ae12dcb7aaa19141814e12ee8168d3dd7213c550123456U:V-U:abcdefgfg16210191418190571250373082114128016210271816270a b c d e f gabcdefgvoid MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法從頂點u出

27、發構造網G的最小生成樹 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔助數組初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; +i) 繼續向生成樹上添加頂點; k = minimum(closedge); / 求出加入生成樹的下一個頂點(k) printf(closedgek.adjvex, G.vexsk); / 輸出生成樹上一條邊 closedgek.lowcost = 0; / 第k頂點

28、并入U集 for (j=0; jG.vexnum; +j) /修改其它頂點的最小邊 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; 具體做法: 先構造一個只含 n 個頂點的子圖 SG，然后從權值最小的邊開始，若它的添加不使SG 中產生回路，則在 SG 上加上這條邊，如此重復，直至加上 n-1 條邊為止。考慮問題的出發點: 為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小。克魯斯卡爾算法的基本思想：abcdegf195141827168213ae12dcbgf714853162

29、1例如:7121819算法描述:構造非連通圖 ST=( V, ); k = i = 0; / k 計選中的邊數 while (kn-1) +i; 檢查邊集 E 中第 i 條權值最小的邊(u,v); 若(u,v)加入ST后不使ST中產生回路， 則 輸出邊(u,v); 且 k+;普里姆算法克魯斯卡爾算法時間復雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應范圍比較兩種算法7.7 拓撲排序 問題: 假設以有向圖表示一個工程的施工圖或程序的數據流圖，則圖中不允許出現回路。 檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。何謂“拓撲排序”？對有向圖進行如下操作： 按照有向圖給出的次序關系

30、，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系。例如：對于下列有向圖BDAC可求得拓撲有序序列： A B C D 或 A C B D由此所得頂點的線性序列稱之為拓撲有序序列BDAC反之，對于下列有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路 B, C, D如何進行拓撲排序？一、從有向圖中選取一個沒有前驅 的頂點，并輸出之； 重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止。二、從有向圖中刪去此頂點以及所 有以它為尾的弧；abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念 沒有前驅的頂點 入度為零的頂點刪除頂點及

31、以它為尾的弧 弧頭頂點的入度減1abcghdfe01234567abcdefgh266734645500112231indegree0 1 2 3 4 5 6 7sab輸出次序:b02hh1a01ccd0dgfe000算法描述Status Topologicalsort(ALGraph G) FindinDegree(G,indegree); InitStack(s) For(i=0;inextarc) k=p-adjvex; if(!(- -indegreek) push(s,k); if(countg.vexnum) return ERROR; 7.8 關鍵路徑問題: 假設以有向網表示一個

32、施工流圖，弧上的權值表示完成該項子工程所需時間。問：哪些子工程項是“關鍵工程”？即：哪些子工程項將影響整個工程的完成期限的。abcdefghk64521187244例如:“關鍵活動”指的是：該弧上的權值增加 將使有向圖上的最長路徑的長度增加。整個工程完成的時間為：從有向圖的源點到匯點的最長路徑。源點匯點6174 如何求關鍵活動？“事件(頂點)” 的 最早發生時間 ve(j)ve(j) = 從源點到頂點j的最長路徑長度；“事件(頂點)” 的 最遲發生時間 vl(k) vl(k) = 從頂點k到匯點的最短路徑長度。 假設第 i 條弧為 則 對第 i 項活動言 “活動(弧)”的 最早開始時間 e(i

33、) e(i) = ve(j)； “活動(弧)”的 最遲開始時間 l(i) l(i) = vl(k) dut()；活動ai的時間余量： l(i) - e(i) 若lk = ek 表示活動ai是關鍵活動。jkai 事件發生時間的計算公式： ve(源點) = 0； ve(k) = Maxve(j) + dut() vl(匯點) = ve(匯點)； vl(j) = Minvl(k) dut()abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓撲有序序列: a - d - f - c - b - e - h

34、 - g - k0645771514181814161078660000645777151414160236688710 算法的實現要點:顯然，求ve的順序應該是按拓撲有序的次序； 而求vl的順序應該是按拓撲逆序的次序；因為拓撲逆序序列即為拓撲有序序列的 逆序列，因此 應該在拓撲排序的過程中， 另設一個“棧”記下拓撲有序序列。 Status TopologicalOrder(ALGraph G,Stack &T) FindinDdegree(G,indegree); InitStack(T); count=0; ve0.G.vexnum-1=0; while(!StackEmpty(S) po

35、p(S,j);Push(T,j); +count; for(p=G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; if(-indegreek=0) Push(S,k); if(vej+*(p-info)=dut() vek=vej+*(p-info); if(countvextarc) k=p-adjvex; dut=*(p-info); if(vlk-dutvlj) vlj=vlk-dut; for(j=0;jnextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-dut; tag=(ee=el)

36、? *: printf(j,k,dut,ee,el,tag); 7.6 兩點之間的 最短路徑問題 求從某個源點到其余各點的最短路徑 每一對頂點之間的最短路徑 求從源點到其余各點的最短路徑的算法的基本思想: 依最短路徑的長度遞增的次序求得各條路徑源點v1其中，從源點到頂點v的最短路徑是所有最短路徑中長度最短者。v2 這條路徑必定是直接從源點到該點v1只含一條弧，并且這條弧的權值最小。 下一條路徑長度次短的最短路徑的特點：路徑長度最短的最短路徑的特點： 它只可能有兩種情況：或者是直接從源點到該點v2(只含一條弧)； 或者是從源點經過頂點v1，再到達該頂點v2(由兩條弧組成)。其余最短路徑的特點：再下一條路徑長度次短的最短路徑的特點: 它可能有三種情況：或者是直接從源點到該點v3(只含一條弧)； 或者是從源點經過頂點v1，再到達該頂點(由兩條弧組成)；或者是從源點經過頂點v2，再到達該頂點v3。 它或者是直