北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu).ppt

1、第7章 圖,第7章 圖,7.1 圖的定義和術(shù)語 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的最小生成樹,第 3 頁,7.1 圖的定義與術(shù)語,一、圖的定義 1、圖(Graph)圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)Α?圖的分類 有向圖 無向圖,第 4 頁,7.1 圖的定義與術(shù)語,2、有向圖有向圖G是由兩個集合V(G)和E(G)組成的。 其中：V(G)是頂點的非空有限集。 E(G)是有向邊（也稱?。┑挠邢藜?，弧是頂點的有序?qū)?，記為，v,w是頂點，v為弧尾，w為弧頭。,第 5 頁,7.

2、1 圖的定義與術(shù)語,例如： G1 = V1 = A, B, C, D, E E1 = , , , , , , ,E,A,C,B,D,第 6 頁,7.1 圖的定義與術(shù)語,3、無向圖無向圖G是由兩個集合V(G)和E(G)組成的。 其中：V(G)是頂點的非空有限集。 E(G)是邊的有限集合，邊是頂點的無序?qū)?，記?(v,w) 或 (w,v)，并且(v,w)=(w,v)。,第 7 頁,7.1 圖的定義與術(shù)語,例如： G2 = V2 = v0 ,v1,v2,v3,v4 E2 = (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) ,V0,V4,V3,

3、V1,V2,第 8 頁,7.1 圖的定義與術(shù)語,例如： G2 = V2 = v0，v1，v2，v3 E2 = , , , ,V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , ,第 9 頁,7.1 圖的定義與術(shù)語,圖的應(yīng)用舉例 例1、交通圖（公路、鐵路） 頂點：地點邊：連接地點的路 例2、電路圖 頂點：元件邊：連接元件之間的線路 例3、通訊線路圖 頂點：地點邊：地點間的連線 例4、各種流程圖 如產(chǎn)品的生產(chǎn)流程圖。 頂點：工序邊：各道工序之間的順序關(guān)系,第 10 頁,7.1 圖的定義與術(shù)語,二、圖的基本術(shù)語 1、鄰接點及關(guān)聯(lián)邊 鄰接點：邊的兩個頂點

4、關(guān)聯(lián)邊：若邊e= (v, u), 則稱頂點v、u 關(guān)聯(lián)邊e 2、頂點的度、入度、出度 頂點V的度 = 與V相關(guān)聯(lián)的邊的數(shù)目 在有向圖中： 頂點V的出度 = 以V為起點有向邊數(shù) 頂點V的入度 = 以V為終點有向邊數(shù) 頂點V的度 = V的出度+V的入度 設(shè)圖G 的頂點數(shù)為 n，邊數(shù)為 e 圖的所有頂點的度數(shù)和 = 2*e （每條邊對圖的所有頂點的度數(shù)和“貢獻(xiàn)”2度）,e,第 11 頁,7.1 圖的定義與術(shù)語,3、路徑、回路 無向圖 G =（V，E）中的頂點序列v1, v2, , vk，若 (vi, vi+1)E ( i=1, 2, , k-1)，v=v1, u=vk，則稱該序列是從頂點v到頂點u的

5、路徑；若v=u，則稱該序列為回路。,路徑：V0, V1, V2, V3 回路：V0, V1, V2, V3, V0,第 12 頁,7.1 圖的定義與術(shù)語,3、路徑、回路 有向圖 D =（V，E）中的頂點序列 v1, v2, , vk，若 E (i=1, 2, , k-1)，v=v1，u=vk，則稱該序列是從頂點v到頂點u的路徑；若v=u，則稱該序列為回路。,路徑：V0, V2, V3 回路：V0, V2, V3, V0,第 13 頁,7.1 圖的定義與術(shù)語,4、連通圖（強連通圖） 在無（有）向圖 G= 中，若對任何兩個頂點 v、u 都存在從 v 到 u 的路徑，則稱G是連通圖（強連通圖）,非連

6、通圖,連通圖,強連通圖,非強連通圖,第 14 頁,7.1 圖的定義與術(shù)語,5、子圖 設(shè)有兩個圖 G=（V，E），G1=（V1，E1），若V1 V，E1 E，而且E1關(guān)聯(lián)的頂點都在 V1 中，則稱 G1 是 G 的子圖；,(b)、(c) 都是 (a) 的子圖,第 15 頁,7.1 圖的定義與術(shù)語,6、連通分量（強連通分量）：無（有）向圖的極大（強）連通子圖。 極大（強）連通子圖：該子圖是（強）連通子圖，若再將G的任何不在該子圖中的頂點加入，子圖就不再（強）連通。,第 16 頁,7.1 圖的定義與術(shù)語,強連通分量,非連通圖,第 17 頁,7.1 圖的定義與術(shù)語,7、生成樹 包含無向圖 G 所有頂點

7、的極小連通子圖稱為G生成樹。 極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。,G1的生成樹,章,連通 所有頂點 無回路,第 18 頁,7.2 圖的存儲結(jié)構(gòu),一、數(shù)組表示法（鄰接矩陣表示） 鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：,在數(shù)組表示法中，用鄰接 矩陣表示頂點間的關(guān)系,第 19 頁,7.2 圖的存儲結(jié)構(gòu),二、鄰接表：圖的鏈?zhǔn)酱鎯Y(jié)構(gòu) 1、無向圖的鄰接表 頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中； 關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲。,第 20 頁,typedef struct tnode /表頭結(jié)點 int vexdata; ArcNode

8、 * firstarc; VNode, AdjList MAX_VERTEX_NUM ;,7.2 圖的存儲結(jié)構(gòu),typedef struct ArcNode/鏈表結(jié)點 int adjvex; struct ArcNode *next; ArcNode;,typedef struct/圖 AdjList vertices; int vexnum, arcnum; / 頂點數(shù)和弧數(shù) int kind; / 圖的種類 ALGraph;,第 21 頁,7.2 圖的存儲結(jié)構(gòu),無向圖的鄰接表的特點 1）在G鄰接表中，同一條邊對應(yīng)兩個結(jié)點； 2）頂點v的度：等于v對應(yīng)線性鏈表的長度； 3）判定兩頂點v ，u

9、是否鄰接：要看v對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點。 4）在G中增減邊：要在兩個單鏈表插入、刪除結(jié)點； 5）設(shè)存儲頂點的一維數(shù)組大小為 m（m圖的頂點數(shù)n），圖的邊數(shù)為 e，G占用存儲空間為：m+2*e。G占用存儲空間與G的頂點數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖。,第 22 頁,7.2 圖的存儲結(jié)構(gòu),2、有向圖的鄰接表 頂點：用一維數(shù)組存儲（按編號順序） 以同一頂點為起點的弧：用線性鏈表存儲,adjvex,next,類似于無向圖的鄰接表，所不同的是： 以同一頂點為起點的?。河镁€性鏈表存儲。,第 23 頁,7.2 圖的存儲結(jié)構(gòu),3、有向圖的逆鄰接表 頂點：用一維數(shù)組存儲（按編號順序） 以同一頂點為終點的

10、?。河镁€性鏈表存儲。,類似于有向圖的鄰接表，所不同的是： 以同一頂點為終點弧：用線性鏈表存儲,章,第 24 頁,7.3 圖的遍歷,連通圖的深度遍歷（DFS） 從圖中某頂點v出發(fā)： 1）訪問頂點v； 2）對v的每個未被訪問的鄰接點wj，從wj出發(fā)，繼續(xù)對圖進(jìn)行深度優(yōu)先遍歷。,深度遍歷： V1,V2,V4,V5,V8,V3,V6,V7,例,深度遍歷： V1,V3,V6,V7,V2,V5,V8,V4,第 25 頁,7.3 圖的遍歷,圖的深度遍歷（DFS）,V,w1,SG1,SG2,SG3,w2,w3,w2,W1、W2和W3 均為 V 的鄰接點，SG1、SG2 和 SG3 分別為含頂點W1、W2和W3

11、 的子圖。,訪問頂點 V ： for (W1、W2、W3 ) 若該鄰接點W未被訪問， 則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。,第 26 頁,7.3 圖的遍歷,圖的深度遍歷（DFS）,V,w1,SG1,SG2,SG3,w2,w3,w2,從圖解可見：,1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；,解決的辦法是：為每個頂點設(shè)立一個 “訪問標(biāo)志 visitedw”。,2. 如何判別V的鄰接點是否被訪問？,第 27 頁,7.3 圖的遍歷,Boolean visitedMAX; / 訪問標(biāo)志數(shù)組 Status (*VisitFunc)(int v); / 訪問函數(shù) void DFS ( Graph

12、G, int v) / 從頂點v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for ( w=FirstAdjVex(G, v);w=0; w=NextAdjVex(G,v,w) ) if ( !visitedw ) DFS(G, w); / 對v的尚未訪問的鄰接頂點w / 遞歸調(diào)用DFS / DFS,第 28 頁,7.3 圖的遍歷,非連通圖的深度優(yōu)先搜索遍歷 首先將圖中每個頂點的訪問標(biāo)志設(shè)為 FALSE，之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。,第 29 頁,7.3 圖的遍歷,voi

13、d DFSTraverse ( Graph G, Status (*Visit) (int v) / 對圖 G 作深度優(yōu)先遍歷。 VisitFunc = Visit; for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 訪問標(biāo)志數(shù)組初始化 for ( v=0; vG.vexnum; +v ) if (!visitedv) DFS(G, v); / 對尚未訪問的頂點調(diào)用DFS ,第 30 頁,7.3 圖的遍歷,例如：,a,b,c,h,d,e,k,f,g,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b

14、,g,a,c,h,k,f,e,d,b,g,訪問標(biāo)志:,訪問次序:,a b c d e f g h k,0 1 2 3 4 5 6 7 8,第 31 頁,7.3 圖的遍歷,圖的深度遍歷（DFS）,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,第 32 頁,7.3 圖的遍歷,圖的廣度遍歷（BFS） 從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。,若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點

15、都被訪問到為止。,第 33 頁,7.3 圖的遍歷,圖的廣度遍歷（BFS） 從圖中某頂點v出發(fā)： 1) 訪問頂點v 2) 訪問v的所有未被訪問的鄰接點w1,w2,wk 3) 依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點，直到圖中所有訪問過的頂點的鄰接點都被訪問到。,V1,V2,V3,V4,V8,V5,V6,V7,V1,V3,V2,V6,V7,V4,V5,V8,第 34 頁,7.3 圖的遍歷,void BFSTraverse ( Graph G, Status (*Visit) (int v) ) for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未訪問 /見下頁 /if / BFSTraverse,第 35 頁,7.3 圖的遍歷,/上頁中的 if 部分 visitedv = TRUE; Visit(v); / 訪問v EnQueue(Q, v); / v入隊列 while (!QueueEmpty(Q) DeQueue(Q, u); / 隊頭元素出隊并置為u f