Ch07 圖形與網路 淡江大學 周清江 1 1 1

7.1 前言 由簡單到複雜，現在要進入“圖形與網路”，更接近實際應用 頂點可代表捷運站，邊則代表連接各站的軌道 由陣列、鏈結串列，到堆疊、佇列，到樹狀結構，資料結構 由簡單到複雜，現在要進入“圖形與網路”，更接近實際應用 頂點可代表捷運站，邊則代表連接各站的軌道 2

7.2 圖形 (Graph) 的基本術語 V 代表圖形 G 中所有頂點 (Vertices) 的集合 E 代表圖形 G 中所有邊 (Edges) 的集合 在圖中，兩頂點如果直接相連，則這兩頂點間有個邊 圖形的邊如有方向性，此圖稱為 有向圖 (Directed Graph) 圖形的邊如無方向性，此圖稱為 無向圖 (Undirected Graph) 3

範例 完全圖 (Complete Graph) 指圖中的每個頂點均與其他頂點直接相連 4

圖形 (Graph) 的基本術語 頂點的分支度 (branching degree) 對有向圖的頂點來說，可細分為： 對無向圖的頂點來說，是連接此頂點的邊的數目 對有向圖的頂點來說，可細分為： 出分支度 (out degree)：此頂點指出去的邊(箭頭)的數目 入分支度 (in degree)：指向此頂點的邊(箭頭)的數目 兩頂點之相鄰 (adjacency) 對無向圖的頂點來說，如果存在一個邊 (a,b) ，則頂點 a 與 頂點 b 為相鄰 對有向圖的頂點來說，如果存在一個邊 <a,b> ，則我們說 頂點 a 可連接到 b 5

範例 6

圖形 (Graph) 的基本術語 兩頂點間的路徑(path) 及路徑長度 (path length) 某個從頂點 a 到頂點 b 所經過的頂點所形成的串列，稱為頂點 a 到頂點 b 的一條路徑，而此路徑所經過的邊數稱為此路徑之長度 兩頂點間可能有很多條路徑 兩頂點間的簡單路徑(simple path) 除了起點與終點外，其餘頂點均只拜訪 1 次之路徑 迴路 (cycle) 起點與終點相同之簡單路徑 子圖 (subgraph) 兩個圖形 G=(V,E) 及 G’=(V’, E’)，如果 V’ 是 V 的子集合，E’ 是 E 的子集合，則稱 G’ 是 G 的子圖 7

範例 8

範例 9

圖形 (Graph) 的基本術語 無向圖： 兩頂點相連(Connected) 如果頂點 a 與 頂點 b 間存在一條以上簡單路徑，則稱頂點 a 與 頂點 b 相連 如果無向圖 G=(V,E) 中，任兩頂點均相連，則稱 G 為相連 圖 (connected graph) 相連子圖 (connected subgraph) 如果無向圖 G 並非相連圖，則 G 是由數個 獨立的 “子圖” 所組 成 (或說 G 可切割成互不相連的 “子圖” )，這些子圖稱為相連 子圖 或 相連單元 (connected component) 10

範例

圖形 (Graph) 的基本術語 有向圖： 如果 G=(V,E) 中，任兩個頂點 a, b 間，存在一條路徑將頂 點 a 連到頂點 b，也存在一條路徑將頂點 b 連到頂點 a，則 我們稱 G 為緊密相連 (strongly connected) 某個有向圖 G 之最大緊密相連子圖 (即再加上其他頂點就 會違反緊密相連) 也叫做緊密相連單元 (strongly connected component) 有向圖 G 可能有幾個緊密相連單元 12

7.3 圖形表示法 相鄰二維矩陣表示法 相鄰二維矩陣表示法 (Adjacent Matrix) 相鄰串列表示法 (Adjacent List) 相鄰複串列 (Adjacent Multi-List) 相鄰二維矩陣表示法 ch7_udgraph_a.java ch7_dgraph_a.java 請將 ch7_udgraph_a.java 改為由檔案輸入圖形頂點 數目及邊等資料 13

相鄰串列表示法 ch7_udgraph_l.java ch7_dgraph_l.java 請將 ch7_dgraph_l.java 改為由檔案輸入圖形頂點 數目及邊等資料 7.3.3 相鄰複串列 (Adjacent Multi-List) 跳過 14

7.4 圖形追蹤 (Graph Traversal，拜訪) 圖形追蹤是指由圖形的某一頂點出發，依照某個規則 ，拜訪其他頂點，直到所有頂點均拜訪過才停止。為 了避免重覆拜訪某些頂點，造成無窮迴圈，我們會對 拜訪過的頂點加上 “已拜訪” 的標記 圖形追蹤可用於 判斷圖形是否為相連圖 找出圖形的相連單元 找到圖形的擴張樹 找到兩頂點間之最短路徑 工作網路與拓撲排序 (topological sort) 先介紹兩種圖形追蹤方法 深度優先 (depth first) 廣度優先 (breadth first) 15

深度優先搜尋 (depth first search, DFS) 選擇圖形 G 的某一個頂點 x 出發，以 “縱向優先” 策略拜訪所有 x 可到達的頂點 步驟 對頂點 x 做一個 “已拜訪” (visited) 的記號。 從與頂點 x 相連且未被拜訪過的頂點中任選一個頂點，假設 挑到頂點 y，對頂點 y 做一個 “已拜訪”的記號，然後以頂 點 y 為新的起點進行深度優先搜尋 [註；此即是遞迴]。 如果步驟 2 找不到與頂點 x 相連且未被拜訪過的頂點，則須 退回到最近拜訪過的頂點，假設為頂點 z ，再以頂點 z 為新 的起點進行深度優先搜尋 。 如果從已拜訪過的頂點都無法再找到未拜訪過的頂點，則結束 搜尋

深度優先搜尋的實作 將與目前拜訪的頂點相連且未被拜訪過的所有頂點以堆 疊存放 步驟 特點 將頂點 x 放進堆疊 當堆疊還有頂點，執行步驟 3 和 4 從堆疊取出一個頂點，假設為頂點 y ，如果 y 還沒被拜訪過，則對頂 點 y 做一個 “已拜訪” (visited) 的記號 將與 y 相連且未被拜訪過的所有頂點放進堆疊 特點 結果非唯一 如果可拜訪到所有頂點，則該圖形為一相連圖，否則就不是相 連圖

深度優先搜尋範例 (ch7_dfs_a.java，有修改過) ch7_dfs_a.java 是以遞迴呼叫 dfs 的方式來完成

廣度優先搜尋 (breadth first search, BFS) 選擇圖形 G 的某一個頂點 x 出發，以 “橫向優先” 策 略拜訪所有 x 可到達的頂點 實作：將與目前拜訪的頂點相連且未被拜訪過的所有頂點以 佇列存放 步驟 將頂點 x 做一個 “已拜訪” (visited) 的記號 將與頂點 x 相連且未被拜訪過的所有頂點放進佇列 當佇列還有頂點，執行步驟 4 由佇列取出一個頂點，假設為頂點 y ，如果 y 還沒被拜訪過，則以頂點 y 為新的起點進行廣度優先搜尋 [註：遞迴] 特徵 結果非唯一 如果可拜訪到所有頂點，則該圖形為一相連圖，否則就不是相連 圖

廣度優先搜尋實作-2 步驟 將頂點 x 做一個 “已拜訪” (visited) 的記號 將與頂點 x 相連且未被拜訪過的所有頂點放進佇列 當佇列還有頂點，執行步驟 4 由佇列取出一個頂點，假設為頂點 y ，如果 y 還沒被拜訪過，則對頂點 y 做一個 “已拜訪” (visited) 的記號，將與 y 相連且未被拜訪過的所有 頂點放進佇列

廣度優先搜尋範例 (ch7_bfs_a.java，有修改過) ch7_bfs_a.java 是以遞迴呼叫 bfs 的方式來完成

作業-2 請將 ch7_udgraph_a.java 改為由檔案輸入圖形資料 請以堆疊 (參考第 4 章 ch4_stack_1.java)實作 DFS 請以佇列 (參考第 4 章 ch4_cqueue.java)實作本講義 p. 20 之 BFS