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

1、第7章 圖第7章 圖 7.1 圖的定義和術(shù)語 7.2 圖的存儲(chǔ)結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的最小生成樹7.1 圖的定義與術(shù)語一、圖的定義1、圖(Graph)圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?。圖的分類 有向圖 無向圖37.1 圖的定義與術(shù)語2、有向圖有向圖G是由兩個(gè)集合V(G)和E(G)組成的。 其中：V(G)是頂點(diǎn)的非空有限集。 E(G)是有向邊（也稱弧）的有限集合，弧是頂點(diǎn)的有序?qū)?，記為，v,w是頂點(diǎn)，v為弧尾，w為弧頭。47.1 圖的定義與術(shù)語例如： G1 = V1 = A

2、, B, C, D, E E1 = , , , , , , EACBD57.1 圖的定義與術(shù)語3、無向圖無向圖G是由兩個(gè)集合V(G)和E(G)組成的。 其中：V(G)是頂點(diǎn)的非空有限集。 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記?(v,w) 或 (w,v)，并且(v,w)=(w,v)。67.1 圖的定義與術(shù)語例如： G2 = V2 = v0 ,v1,v2,v3,v4 E2 = (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) V0V4V3V1V277.1 圖的定義與術(shù)語例如： G2 = V2 = v0，v1，v2，v3 E2 = ,

3、 , , V0 V1 V2 V3 例245136G1V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , 87.1 圖的定義與術(shù)語圖的應(yīng)用舉例例1、交通圖（公路、鐵路） 頂點(diǎn)：地點(diǎn)邊：連接地點(diǎn)的路例2、電路圖 頂點(diǎn)：元件邊：連接元件之間的線路例3、通訊線路圖 頂點(diǎn)：地點(diǎn)邊：地點(diǎn)間的連線例4、各種流程圖如產(chǎn)品的生產(chǎn)流程圖。 頂點(diǎn)：工序邊：各道工序之間的順序關(guān)系97.1 圖的定義與術(shù)語二、圖的基本術(shù)語1、鄰接點(diǎn)及關(guān)聯(lián)邊 鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn) 關(guān)聯(lián)邊：若邊e= (v, u), 則稱頂點(diǎn)v、u 關(guān)聯(lián)邊e2、頂點(diǎn)的度、入度、出度 頂點(diǎn)V的度 = 與V相關(guān)聯(lián)的邊

4、的數(shù)目 在有向圖中： 頂點(diǎn)V的出度 = 以V為起點(diǎn)有向邊數(shù) 頂點(diǎn)V的入度 = 以V為終點(diǎn)有向邊數(shù) 頂點(diǎn)V的度 = V的出度+V的入度 設(shè)圖G 的頂點(diǎn)數(shù)為 n，邊數(shù)為 e 圖的所有頂點(diǎn)的度數(shù)和 = 2*e （每條邊對圖的所有頂點(diǎn)的度數(shù)和“貢獻(xiàn)”2度） V0 V4 V3 V1 V2eV0V1V2V3107.1 圖的定義與術(shù)語3、路徑、回路 無向圖 G =（V，E）中的頂點(diǎn)序列v1, v2, , vk，若 (vi, vi+1)E ( i=1, 2, , k-1)，v=v1, u=vk，則稱該序列是從頂點(diǎn)v到頂點(diǎn)u的路徑；若v=u，則稱該序列為回路。無向圖G1 V0 V4 V3 V1 V2路徑：V0,

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

6、 V3 V0 V2 V3 V1 V5 V4 V0 V4 V3 V1 V2 V0 V1 V2 V3137.1 圖的定義與術(shù)語5、子圖 設(shè)有兩個(gè)圖 G=（V，E），G1=（V1，E1），若V1 V，E1 E，而且E1關(guān)聯(lián)的頂點(diǎn)都在 V1 中，則稱 G1 是 G 的子圖；(b)、(c) 都是 (a) 的子圖(d) V4 V1 V2(c) V0 V4 V3 V1 V2(a) V0 V4 V3 V1 V2(b) V0 V4 V3 V1 V2147.1 圖的定義與術(shù)語6、連通分量（強(qiáng)連通分量）：無（有）向圖的極大（強(qiáng)）連通子圖。極大（強(qiáng)）連通子圖：該子圖是（強(qiáng)）連通子圖，若再將G的任何不在該子圖中的頂點(diǎn)加

7、入，子圖就不再（強(qiáng)）連通。非連通圖 V0 V2 V3 V1 V5 V4連通分量157.1 圖的定義與術(shù)語強(qiáng)連通分量 V0 V1 V2 V3非連通圖 V0 V2 V3 V1167.1 圖的定義與術(shù)語7、生成樹 包含無向圖 G 所有頂點(diǎn)的極小連通子圖稱為G生成樹。 極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。G1的生成樹 V0 V4 V3 V1 V2章連通圖G1 V0 V4 V3 V1 V2 連通 所有頂點(diǎn) 無回路17 V0 V1 V2 V37.2 圖的存儲(chǔ)結(jié)構(gòu)一、數(shù)組表示法（鄰接矩陣表示）鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：Aij=1 若(vi,

8、vj)E 或 E0 否則0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系 V0 V4 V3 V1 V20 1 1 00 0 0 00 0 0 11 0 0 0187.2 圖的存儲(chǔ)結(jié)構(gòu)二、鄰接表：圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1、無向圖的鄰接表 頂點(diǎn)：通常按編號(hào)順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中； 關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ)。 V0 V4 V3 V1 V2 0 1 2 3 4m-1V0V1V2V3V413212013420419typedef struct tnode /表頭結(jié)點(diǎn) int vexdata; ArcNode *

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

10、； 3）判定兩頂點(diǎn)v ，u是否鄰接：要看v對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點(diǎn)。 4）在G中增減邊：要在兩個(gè)單鏈表插入、刪除結(jié)點(diǎn)； 5）設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為 m（m圖的頂點(diǎn)數(shù)n），圖的邊數(shù)為 e，G占用存儲(chǔ)空間為：m+2*e。G占用存儲(chǔ)空間與G的頂點(diǎn)數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖。217.2 圖的存儲(chǔ)結(jié)構(gòu)2、有向圖的鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)0123v0v2v3v1vexdatafirstarc 2 1 3 0adjvexnext類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)。V0V1V2V3227.2 圖的存儲(chǔ)結(jié)構(gòu)3、

11、有向圖的逆鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存儲(chǔ)。0123v0v2v3v1vexdatafirstarc 3 0 0 2類似于有向圖的鄰接表，所不同的是：以同一頂點(diǎn)為終點(diǎn)?。河镁€性鏈表存儲(chǔ)V0V1V2V3章237.3 圖的遍歷連通圖的深度遍歷（DFS）從圖中某頂點(diǎn)v出發(fā)： 1）訪問頂點(diǎn)v； 2）對v的每個(gè)未被訪問的鄰接點(diǎn)wj，從wj出發(fā)，繼續(xù)對圖進(jìn)行深度優(yōu)先遍歷。深度遍歷： V1,V2,V4,V5,V8,V3,V6,V7 例 V1 V8 V7 V6 V5 V4 V3 V2V1V2V4V3V8V7V6 V5深度遍歷： V1,V3,V6,V7,V2,V5,V8

12、,V4247.3 圖的遍歷圖的深度遍歷（DFS）Vw1SG1SG2SG3w2w3w2 W1、W2和W3 均為 V 的鄰接點(diǎn)，SG1、SG2 和 SG3 分別為含頂點(diǎn)W1、W2和W3 的子圖。訪問頂點(diǎn) V ：for (W1、W2、W3 ) 若該鄰接點(diǎn)W未被訪問， 則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。257.3 圖的遍歷圖的深度遍歷（DFS）Vw1SG1SG2SG3w2w3w2從圖解可見：1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問標(biāo)志 visitedw”。2. 如何判別V的鄰接點(diǎn)是否被訪問？267.3 圖的遍歷Boolean visitedMAX;

13、 / 訪問標(biāo)志數(shù)組Status (*VisitFunc)(int v); / 訪問函數(shù)void DFS ( Graph G, int v) / 從頂點(diǎn)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的尚未訪問的鄰接頂點(diǎn)w / 遞歸調(diào)用DFS / DFS277.3 圖的遍歷非連通圖的深度優(yōu)先搜索遍歷 首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE，之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問

14、，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。287.3 圖的遍歷void 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ǎn)調(diào)用DFS297.3 圖的遍歷例如：abchdekfgF F F F F F F F FTTTTTT

15、TTTachdkfe bgachkfedbg訪問標(biāo)志:訪問次序: a b c d e f g h k 0 1 2 3 4 5 6 7 8307.3 圖的遍歷圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍歷：V1V3 V7 V6 V2 V4 V8 V5317.3 圖的遍歷圖的廣度遍歷（BFS） 從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被

16、訪問到。 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。327.3 圖的遍歷圖的廣度遍歷（BFS）從圖中某頂點(diǎn)v出發(fā)：1) 訪問頂點(diǎn)v2) 訪問v的所有未被訪問的鄰接點(diǎn)w1,w2,wk3) 依次從這些鄰接點(diǎn)出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn)，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問到。V1V8V7V6V5V4V3V2V1 V2 V4 V3 V8 V7 V6 V5V1,V2,V3,V4,V8,V5,V6,V7V1,V3,V2,V6,V7,V4,V5,V8337.3 圖的遍歷void BFSTraverse ( Graph G,

17、 Status (*Visit) (int v) ) for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; v=0; w=NextAdjVex(G,u,w) ) if ( ! visitedw ) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點(diǎn)w入隊(duì)列 / if / while357.3 圖的遍歷圖的廣度遍歷（BFS）（請對照教材第170頁）例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：10 1 2 3 4 54fr遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：1 4 3367.3 圖的遍歷圖的廣度遍歷（BFS）例142350 1 2 3 4 54 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序