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

《北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu).ppt》由會員分享，可在線閱讀，更多相關(guān)《北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu).ppt（38頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第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 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 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)邊鄰接點 邊的兩個頂點關(guān)聯(lián)邊 若邊e v u 則稱頂點v u關(guān)聯(lián)邊e2 頂點的度 入度 出度頂點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ù)和 貢獻 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的路徑 若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是連通圖 強連通圖 非連通圖 連通圖 強連通圖 非強連通圖 第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所有頂點的極小連通子圖稱為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頁 typedefstructtnode 表頭結(jié)點 intvexdata ArcNode firstarc VNode AdjList MAX VERTEX NUM 7 2圖的存儲結(jié)構(gòu) typedefstructArcNode 鏈表結(jié)點 intadjvex structArcNode next ArcNode typedefstruct 圖 AdjListvertices intvexnum arcnum 頂點數(shù)和弧數(shù)intkind 圖的種類 ALGraph 第21頁 7 2圖的存儲結(jié)構(gòu) 無向圖的鄰接表的特點1 在G鄰接表中 同一條邊對應(yīng)兩個結(jié)點 2 頂點v的度 等于v對應(yīng)線性鏈表的長度 3 判定兩頂點v u是否鄰接 要看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ù)組存儲 按編號順序 以同一頂點為終點的弧 用線性鏈表存儲 類似于有向圖的鄰接表 所不同的是 以同一頂點為終點弧 用線性鏈表存儲 章 第24頁 7 3圖的遍歷 連通圖的深度遍歷 DFS 從圖中某頂點v出發(fā) 1 訪問頂點v 2 對v的每個未被訪問的鄰接點wj 從wj出發(fā) 繼續(xù)對圖進行深度優(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的子圖 訪問頂點V for W1 W2 W3 若該鄰接點W未被訪問 則從它出發(fā)進行深度優(yōu)先搜索遍歷 第26頁 7 3圖的遍歷 圖的深度遍歷 DFS V w1 SG1 SG2 SG3 w2 w3 w2 從圖解可見 1 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷 解決的辦法是 為每個頂點設(shè)立一個 訪問標(biāo)志visited w 2 如何判別V的鄰接點是否被訪問 第27頁 7 3圖的遍歷 Booleanvisited MAX 訪問標(biāo)志數(shù)組Status VisitFunc intv 訪問函數(shù)voidDFS GraphG intv 從頂點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 對v的尚未訪問的鄰接頂點w 遞歸調(diào)用DFS DFS 第28頁 7 3圖的遍歷 非連通圖的深度優(yōu)先搜索遍歷首先將圖中每個頂點的訪問標(biāo)志設(shè)為FALSE 之后搜索圖中每個頂點 如果未被訪問 則以該頂點為起始點 進行深度優(yōu)先搜索遍歷 否則繼續(xù)檢查下一頂點 第29頁 7 3圖的遍歷 voidDFSTraverse GraphG Status Visit intv 對圖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 對尚未訪問的頂點調(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 從圖中的某個頂點V0出發(fā) 并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點 之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點 直至圖中所有和V0有路徑相通的頂點都被訪問到 若此時圖中尚有頂點未被訪問 則另選圖中一個未曾被訪問的頂點作起始點 重復(fù)上述過程 直至圖中所有頂點都被訪問到為止 第33頁 7 3圖的遍歷 圖的廣度遍歷 BFS 從圖中某頂點v出發(fā) 1 訪問頂點v2 訪問v的所有未被訪問的鄰接點w1 w2 wk3 依次從這些鄰接點出發(fā) 訪問它們的所有未被訪問的鄰接點 直到圖中所有訪問過的頂點的鄰接點都被訪問到 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 置空的輔助隊列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入隊列while QueueEmpty Q DeQueue Q u 隊頭元素出隊并置為ufor w FirstAdjVex G u w 0 w NextAdjVex G u w if visited w visited w TRUE Visit w EnQueue Q w 訪問的頂點w入隊列 if while 第36頁 7 3圖的遍歷 圖的廣度遍歷 BFS 請對照教材第170頁 第37頁 7 3圖的遍歷 圖的廣度遍歷 BFS 第38頁 7 3圖的遍歷 圖的廣度遍歷 BFS 遍歷序列 14325 章