第7章圖 第7章圖 7 1圖的定義和術(shù)語7 2圖的存儲(chǔ)結(jié)構(gòu)7 3圖的遍歷7 4圖的最小生成樹 第3頁 7 1圖的定義與術(shù)語 一 圖的定義1 圖 Graph 圖G是由兩個(gè)集合V G 和E G 組成的 記為G V E 其中 V G 是頂點(diǎn)的非空有限集E G 是邊的有限集合 邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?圖的分類有向圖無向圖 第4頁 7 1圖的定義與術(shù)語 2 有向圖 有向圖G是由兩個(gè)集合V G 和E G 組成的 其中 V G 是頂點(diǎn)的非空有限集 E G 是有向邊 也稱弧 的有限集合 弧是頂點(diǎn)的有序?qū)?記為 v w是頂點(diǎn) v為弧尾 w為弧頭 第5頁 7 1圖的定義與術(shù)語 例如 G1 V1 A B C D E E1 E A C B D 第6頁 7 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 第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 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 交通圖 公路 鐵路 頂點(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)系 第10頁 7 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)的邊的數(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 每條邊對(duì)圖的所有頂點(diǎn)的度數(shù)和 貢獻(xiàn) 2度 e 第11頁 7 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 則稱該序列為回路 路徑 V0 V1 V2 V3回路 V0 V1 V2 V3 V0 第12頁 7 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 則稱該序列為回路 路徑 V0 V2 V3回路 V0 V2 V3 V0 第13頁 7 1圖的定義與術(shù)語 4 連通圖 強(qiáng)連通圖 在無 有 向圖G 中 若對(duì)任何兩個(gè)頂點(diǎn)v u都存在從v到u的路徑 則稱G是連通圖 強(qiáng)連通圖 非連通圖 連通圖 強(qiáng)連通圖 非強(qiáng)連通圖 第14頁 7 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 的子圖 第15頁 7 1圖的定義與術(shù)語 6 連通分量 強(qiáng)連通分量 無 有 向圖的極大 強(qiáng) 連通子圖 極大 強(qiáng) 連通子圖 該子圖是 強(qiáng) 連通子圖 若再將G的任何不在該子圖中的頂點(diǎn)加入 子圖就不再 強(qiáng) 連通 第16頁 7 1圖的定義與術(shù)語 強(qiáng)連通分量 非連通圖 第17頁 7 1圖的定義與術(shù)語 7 生成樹包含無向圖G所有頂點(diǎn)的極小連通子圖稱為G生成樹 極小連通子圖意思是 該子圖是G的連通子圖 在該子圖中刪除任何一條邊 子圖不再連通 G1的生成樹 章 連通所有頂點(diǎn)無回路 第18頁 7 2圖的存儲(chǔ)結(jié)構(gòu) 一 數(shù)組表示法 鄰接矩陣表示 鄰接矩陣 G的鄰接矩陣是滿足如下條件的n階矩陣 在數(shù)組表示法中 用鄰接矩陣表示頂點(diǎn)間的關(guān)系 第19頁 7 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ǔ) 第20頁 typedefstructtnode 表頭結(jié)點(diǎn) intvexdata ArcNode firstarc VNode AdjList MAX VERTEX NUM 7 2圖的存儲(chǔ)結(jié)構(gòu) typedefstructArcNode 鏈表結(jié)點(diǎn) intadjvex structArcNode next ArcNode typedefstruct 圖 AdjListvertices intvexnum arcnum 頂點(diǎn)數(shù)和弧數(shù)intkind 圖的種類 ALGraph 第21頁 7 2圖的存儲(chǔ)結(jié)構(gòu) 無向圖的鄰接表的特點(diǎn)1 在G鄰接表中 同一條邊對(duì)應(yīng)兩個(gè)結(jié)點(diǎn) 2 頂點(diǎn)v的度 等于v對(duì)應(yīng)線性鏈表的長(zhǎng)度 3 判定兩頂點(diǎn)v u是否鄰接 要看v對(duì)應(yīng)線性鏈表中有無對(duì)應(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) 適用于邊稀疏的圖 第22頁 7 2圖的存儲(chǔ)結(jié)構(gòu) 2 有向圖的鄰接表頂點(diǎn) 用一維數(shù)組存儲(chǔ) 按編號(hào)順序 以同一頂點(diǎn)為起點(diǎn)的弧 用線性鏈表存儲(chǔ) adjvex next 類似于無向圖的鄰接表 所不同的是 以同一頂點(diǎn)為起點(diǎn)的弧 用線性鏈表存儲(chǔ) 第23頁 7 2圖的存儲(chǔ)結(jié)構(gòu) 3 有向圖的逆鄰接表頂點(diǎn) 用一維數(shù)組存儲(chǔ) 按編號(hào)順序 以同一頂點(diǎn)為終點(diǎn)的弧 用線性鏈表存儲(chǔ) 類似于有向圖的鄰接表 所不同的是 以同一頂點(diǎn)為終點(diǎn)弧 用線性鏈表存儲(chǔ) 章 第24頁 7 3圖的遍歷 連通圖的深度遍歷 DFS 從圖中某頂點(diǎn)v出發(fā) 1 訪問頂點(diǎn)v 2 對(duì)v的每個(gè)未被訪問的鄰接點(diǎn)wj 從wj出發(fā) 繼續(xù)對(duì)圖進(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的鄰接點(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)先搜索遍歷 第26頁 7 3圖的遍歷 圖的深度遍歷 DFS V w1 SG1 SG2 SG3 w2 w3 w2 從圖解可見 1 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷 解決的辦法是 為每個(gè)頂點(diǎn)設(shè)立一個(gè) 訪問標(biāo)志visited w 2 如何判別V的鄰接點(diǎn)是否被訪問 第27頁 7 3圖的遍歷 Booleanvisited MAX 訪問標(biāo)志數(shù)組Status VisitFunc intv 訪問函數(shù)voidDFS GraphG intv 從頂點(diǎn)v出發(fā) 深度優(yōu)先搜索遍歷連通圖Gvisited v TRUE VisitFunc v for w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS G w 對(duì)v的尚未訪問的鄰接頂點(diǎn)w 遞歸調(diào)用DFS DFS 第28頁 7 3圖的遍歷 非連通圖的深度優(yōu)先搜索遍歷首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為FALSE 之后搜索圖中每個(gè)頂點(diǎn) 如果未被訪問 則以該頂點(diǎn)為起始點(diǎn) 進(jìn)行深度優(yōu)先搜索遍歷 否則繼續(xù)檢查下一頂點(diǎn) 第29頁 7 3圖的遍歷 voidDFSTraverse GraphG Status Visit intv 對(duì)圖G作深度優(yōu)先遍歷 VisitFunc Visit for v 0 v G vexnum v visited v FALSE 訪問標(biāo)志數(shù)組初始化for v 0 v G vexnum v if visited v DFS G v 對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS 第30頁 7 3圖的遍歷 例如 a b c h d e k f g FFFFFFFFF T T T T T T T T T a c h d k f e b g a c h k f e d b g 訪問標(biāo)志 訪問次序 abcdefghk 012345678 第31頁 7 3圖的遍歷 圖的深度遍歷 DFS 深度遍歷 V1 V3 V7 V6 V2 V4 V8 V5 第32頁 7 3圖的遍歷 圖的廣度遍歷 BFS 從圖中的某個(gè)頂點(diǎn)V0出發(fā) 并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn) 之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn) 直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到 若此時(shí)圖中尚有頂點(diǎn)未被訪問 則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn) 重復(fù)上述過程 直至圖中所有頂點(diǎn)都被訪問到為止 第33頁 7 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)都被訪問到 V1 V2 V3 V4 V8 V5 V6 V7 V1 V3 V2 V6 V7 V4 V5 V8 第34頁 7 3圖的遍歷 voidBFSTraverse GraphG Status Visit intv for v 0 v G vexnum v visited v FALSE 初始化訪問標(biāo)志InitQueue Q 置空的輔助隊(duì)列Qfor v 0 v G vexnum v if visited v v尚未訪問 見下頁 if BFSTraverse 第35頁 7 3圖的遍歷 上頁中的if 部分visited v TRUE Visit v 訪問vEnQueue Q v v入隊(duì)列while QueueEmpty Q DeQueue Q u 隊(duì)頭元素出隊(duì)并置為ufor w FirstAdjVex G u w 0 w NextAdjVex G u w if visited w visited w TRUE Visit w EnQueue Q w 訪問的頂點(diǎn)w入隊(duì)列 if while 第36頁 7 3圖的遍歷 圖的廣度遍歷 BFS 請(qǐng)對(duì)照教材第170頁 第37頁 7 3圖的遍歷 圖的廣度遍歷 BFS 第38頁 7 3圖的遍歷 圖的廣度遍歷 BFS 遍歷序列 14325 章