鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第八章：圖（Graph） 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

簡介 以圖形作為問題的抽象化表現 應用圖形理論（Graph Theory）解決問題 2019/5/8

七橋問題：走過所有的橋一次再回原點 2019/5/8

七橋問題：抽象化 尤拉迴路（Eulerian Cycle） 在一個圖之中，是否存在一個路徑，可從一個點出發，走過每一個邊恰好一次，再回到出發點？ 2019/5/8

問題的圖形表示法 尤拉迴路（Eulerian Cycle） 在一個圖之中，是否存在一個路徑，可從一個點出發，走過每一個邊恰好一次，再回到出發點？ 必須所有的點Degree都為偶數方可！ 2019/5/8

圖形專有名詞 G=(V,E) V: vertex（點、節點、頂點） E: edge（邊、連線） V={v1,v2,v3,…,vn}, n>0 E: edge（邊、連線） E={e1,e2,e3,…,em},m>0 2019/5/8

圖形專有名詞 無方向圖形（Undirected Graph） 有方向圖形（Directed Graph） Edge 沒有方向性 e1=(v1,v2) 、 e1=(v2,v1) 相同 有方向圖形（Directed Graph） Edge 有方向性 e1=<v1,v2> 與 e2=<v2,v1> 不同 e1=<v1,v2>，v1為頭（head），v2為尾（tail），方向為：從v1指向v2 2019/5/8

圖形專有名詞 多重圖形（Multigraph） 兩個頂點之間，有多條相同的邊 2019/5/8

圖形專有名詞 完整圖形（Complete Graph） 無向圖若有n個頂點，則有n(n-1)/2個邊 每一對頂點之間都有一個邊使之相連 有向圖若有n個頂點，則有n(n-1)個邊 每一對頂點之間都有一來一去的兩個邊使之相連 2019/5/8

圖形專有名詞 相鄰（Adjacent） 無向圖G=(V,E) 有向圖G=(V,E) u,vV，(u,v)E 稱頂點 u 與頂點 v 相鄰 稱 u 相鄰至（Adjacent To）v 稱 v 相鄰自（Adjacent From）u 2019/5/8

圖形專有名詞 附著（Incident） 若 u, v 兩頂點相鄰 則稱邊(u,v)附著於頂點u （同樣也有：邊(u,v)附著於頂點v） 2019/5/8

圖形專有名詞 子圖（Sub-graph） 若 G’=(V’,E’) 是 G=(V,E) 的子圖，則 pp. 498 V’V E’E 2019/5/8

圖形專有名詞 路徑（Path） 一條從u到v的路徑 路徑長度（Path Length） 簡單路徑（Simple Path） 由頂點u,v1,v2,v3,…vk-1,v與邊(u,v1),(v1,v2),(v2,v3),…,(vk-1,v)所構成 路徑長度（Path Length） 路徑長度 k 為路徑上的邊（Edge）的數量 簡單路徑（Simple Path） 除了起點u與終點v之外，路徑上的頂點皆不相同（路徑中沒有交叉點） 2019/5/8

圖形專有名詞 循環（Cycle）又稱：迴圈 Acyclic（沒有迴圈） 起點與終點相同的簡單路徑 圖中沒有迴圈（Cycle） A tree is an acyclic graph 2019/5/8

圖形專有名詞 連通（Connected） 連通圖形（Connected Graph） 連通單元（Connected Component） 若頂點u與v連通，則 存在一簡單路徑連接u與v 連通圖形（Connected Graph） G=(V,E)中，每一對頂點都互相連通 連通單元（Connected Component） 圖中最大的連通子圖（Maximal Connected Subgraph） 2019/5/8

圖形專有名詞 緊密連通（Strongly Connected） 緊密連通單元（Strongly Connected Component） 有相向圖形（Directed Graph）之中，每一對頂點 u, v 之間都有一條從 u 到 v 的路徑以及一條從 v 到 u 的路徑（Directed Graph） 緊密連通單元（Strongly Connected Component） 緊密連通最大子圖 2019/5/8

圖形專有名詞 分支度（Degree） 無向圖G=(V,E) 有向圖G=(V,E) uV 頂點 u 的分支度=附著於 u 的邊的總數 vV 頂點 v 的向內分支度（in-degree）=以 v 為尾的邊的總數 （箭頭指向 v） 頂點 v 的向外分支度（out-degree）=以 v 為頭的邊的總數 （箭頭從 v 指出去） 2019/5/8

圖形專有名詞 無向圖G=(V,E) V={v1,v2,v3,…,vn}, n>0 E={e1,e2,e3,…,em},m>0 令 d(vi) 為 vi 的分支度，則 2019/5/8

圖形專有名詞 在本章之中若無特別說明，則所述之圖為無向圖，且有下列限制： 不允許任何頂點有連接自己的邊 (v,v) （Self-loop） 相同的邊不得重複（multigraph） 2019/5/8

圖形表示法 相鄰矩陣（Adjacent Matrix） 矩陣A[u][v] = 0 表示邊(u,v)不存在 無向圖的相鄰矩陣以對角線對稱，A[u][v]=A[v][u] G=(V,E),|V|=n, 頂點 iV 的分支度（Degree） 無向圖 有向圖 2019/5/8

圖形表示法 相鄰串列（Adjacent List） 反向相鄰串列（Inverse Adjacent List） 以鍵結串列儲存與頂點u相鄰的其他頂點 需要|V|個鍵結串列 反向相鄰串列（Inverse Adjacent List） 各頂點將相鄰到他自己的頂點以鍵結串列儲存起來（Directed Graph） 2019/5/8

圖形的搜尋或走訪（DFS） 深先搜尋（depth-first search）縱向優先 使用 Stack 時間複雜度： 使用 Adjacent Matrix: O(n2) 使用 Adjacent List: O(n+e), n=|V|, e=|E| 當 n > e 時為O(n) 當 e > n 時為O(e) 需用一個一維陣列 visited 紀錄走過的路徑 2019/5/8

Depth-First Search (DFS) 先拜訪起點 v 選擇一個與 v 相鄰而且尚未被拜訪過的節點 w，以 w 為起點執行 DFS 若一頂點的所有相鄰頂點都已經被拜訪過了，則退回到最近曾拜訪過的頂點，針對與該頂點相鄰且尚未被拜訪過的頂點執行 DFS 若從任何已走過的頂點，都無法再找到未被拜訪過的頂點，則結束 DFS 2019/5/8

圖形的搜尋或走訪：BFS 廣先搜尋（breadth-first search）橫向優先 使用 Queue 需用一個一維陣列 visited 紀錄走過的路徑 2019/5/8

Breadth-First Search (BFS) 1. 準備一個佇列 Q 2. 將起始頂點 v 加入到 Q 之中（Enqueue） 3. 若 Q 不是空的，則執行下列步驟，否則跳到步驟 4： 3.1 從 Q 取出一頂點 w（Dequeue） 3.2 將 w 標示為『已拜訪過』 3.3 將所有與 w 相鄰且尚未標示『已拜訪過』的頂點加入到 Q 之中（Enqueue） 3.4 回到步驟 3 4. 結束 2019/5/8

尋找圖形的連通組合 Find connected components for (i = 0; i < n; i++) visited[i] = 0; if (visited[i] == 0) DFS(i); 2019/5/8

擴展樹 Spanning Tree G=(V,E) is connected T=(V,ET), ETE contains edges visited in some DFS or BFS 以 DFS 產生的擴展樹：DFS 擴展樹 以 BFS 產生的擴展樹：BFS 擴展樹 2019/5/8

最小成本擴展樹 Minimum Cost Spanning Tree Weighted graph G=(V,E) T=(V,ET), ET 所有邊的成本加總值為最小 Prim’s Algorithm: Greedy Method 每次加入一個距離最近的相鄰頂點（及附著的邊），直到所有的頂點都加入為止 O(n2) Kruskal’s Algorithm: Greedy Method 每次挑選一個 Weight 最小的邊，但不可形成迴圈，直到數量達 n-1 個邊為止 O(e log e) or O(n2 log n) e = O(n2) 2019/5/8

最短路徑（Shortest Path） 單一起點至其他頂點（Single Source/All Destination） Dijkstra’s Algorithm O(n2) 任意兩點之間（All Pairs） 輪流以每一個頂點做一次Dijkstra Dynamic Programming A[i][j] = min(A[i][j], A[i][k] + A[k][j]), 0<=k<=n-1 O(n3) 2019/5/8

Dijkstra’s Algorithm D[i] = A[F, i], i=1,N（F 為起始頂點，A[F, i] 為頂點 F 到頂點 i 的距離） S={F} V={1,2,3,…,N} 若 V-S 不是空集合，執行下列步驟，否則跳到步驟 3： 在 V-S 集合中找一頂點 t 使得 D[t] 為最小值，並將 t 加入 S 對於所有與 t 相鄰的頂點 i，調整 D[i] = min(D[i], D[t]+A[t, i]) 結束 2019/5/8

遞移封閉 （Transitive Closure） aRb AND bRc => aRc R: relation A+[i][j]=A+[i][j] || A+[i][k] && A+[k][j] 有向圖：測試連通性 2019/5/8

拓樸排序 （Topological Sort） AOV Network: Activity-on-Vertex Network 頂點代表工作（Task）或活動（Activity） 邊代表工作之間的順序關係（Precedence Relations） <u,v> u: immediate predecessor 前行者 v: immediate successor 後繼者 Transitive: a,b,cA, ab AND bc => ac 目的：排出工作執行的順序 2019/5/8

Topological Sort 演算法 在 AOV Network 中任意挑選沒有前行者的頂點 輸出此頂點，並將此頂點所連接的邊刪除 重複步驟 1, 2 直到全部的頂點都輸出為止 2019/5/8

臨界路徑法 Critical Path Method AOE Network: 邊（Edge）代表活動（Activity） 計畫績效評估 完成計畫所需的最短時間 為縮短整個計畫執行時間，那一些工作必須投入較多的資源？ 專案評估與技術查核 Project Evaluation and Review Technique, PERT 計畫完工所需的最少時間 AOE Network 上從起始點到結束點的最長路徑 評估每一件工作的最早開始時間與最晚完成時間 Critical Activity：最早開始時間=最晚完成時間 表示完全不允許延誤 臨界路徑 Critical Path 2019/5/8

臨界路徑法 最早開始時間 Earliest Start Time 最晚完成時間 Latest Completion Time 先設ES[i] = 0，在 Topological Sort 過程中修正： ES(k) = max( ES(k), ES(j)+<j,k>時間 ) 最晚完成時間 Latest Completion Time LC(k) = min( LC(k), LC(j)-<j,k>時間 ) 2019/5/8