Elementary Graph Algorithms

Slides:



Advertisements
Similar presentations
動畫與遊戲設計 Data structure and artificial intelligent
Advertisements

Chapter 10 Graphs.
Chapter 12 圖形結構 12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹
資料結構與C++程式設計進階 資料結構概論 講師:林業峻 CSIE, NTU 6/ 7, 2010.
第7章 图论基础与应用 PART A 《可视化计算》.
Minimum Spanning Trees
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
GRAPH THEORY 圖論 第二組 晏彩霞 陳弘益 王文斕.
Chap5 Graph.
7.5 擴張樹 (Spanning Tree) 一個無向相連圖 G 的子圖 G’ 如果可用最少的邊來連接G 的
Chapter 4 歸納(Induction)與遞迴(Recursion)
微積分網路教學課程 應用統計學系 周 章.
Chapter 4 Spanning Trees
Chap5 Graph.
樹狀結構 陳怡芬 2018/11/16 北一女中資訊專題研究.
非線性規劃 Nonlinear Programming
第8章 圖形結構(Graphs) 8-1 圖形的基本觀念 8-2 圖形的表示法 8-3 圖形的走訪 8-4 擴張樹
Chapter 6 Graph Chang Chi-Chung
The Greedy Method.
演算法方式總覽 The Divide-and-Conquer Strategy (個各擊破)(binary Searching、Quick Sort…. ) The Greedy Method(貪婪演算法) (Prim MST、Kruskal MST、Djikstra's algorithm) Dynamic.
圖論 (Graph Theory) B 電機四 大鳥 B 電機四 酋長 B 電機四 炫大
第4章 网络互联与广域网 4.1 网络互联概述 4.2 网络互联设备 4.3 广域网 4.4 ISDN 4.5 DDN
Graph 2 Michael Tsai 2012/5/1 連載: 學生上課睡覺姿勢大全
Course 9 NP Theory序論 An Introduction to the Theory of NP
Graph Theory Graph theory is the study of the properties of graph structures. It provides us with a language with which to talk about graphs.
Chapter 5 Fundamental Properties of Graphs and Digraphs
Chapter 7 圖形與網路 資料結構導論 - C語言實作.
資料結構 第7章 圖形結構.
Data Structure.
Chap3 Linked List 鏈結串列.
Chapter12 Graphs Definitions Applications Properties
Yuzhong Qu Nanjing University
Ch 3 Dynamic Programming (動態規劃).
深度優先搜尋(DFS)與 廣度優先搜尋(BFS)
樹 2 Michael Tsai 2013/3/26.
Ch07 圖形與網路 淡江大學 周清江
Chapter 2 Basic Concepts in Graph Theory
感謝同學們在加分題建議. 我會好好研讀+反省~
Chapter 5 Recursion.
第9章 基本图算法 本章内容将包含基本的图形表示法,以及先深搜寻,先广搜寻,拓朴排序,Strongly Connected Components。
資料結構 優點 缺點 1 陣列 (Array) 沒有額外變量 (例head, next,...) 運作/操作較簡單 更新資料時,若要保持順序,需要移動較大量資料 靜態結構Static (宣告時已決定了陣列元素多少,不能在程式執行期間增減元素) 2 隊列Queue (FIFO) 容易更新 加入enqueue:
每周三交作业,作业成绩占总成绩的15%; 平时不定期的进行小测验,占总成绩的 15%;
最短路徑 The Shortest Path.
3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19.
计算机问题求解 – 论题 算法方法 2016年11月28日.
101北一女中 資訊選手培訓營 深度優先搜尋(DFS)的進階應用 Nan.
圖論的介紹 第二組 徐榮德 鄭又齊 陳俊嘉.
第15讲 路与回路, 图的连通性 主要内容: 1.路与回路. 2.图的连通性..
103資訊學科培訓 圖論 - BFS & DFS & 應用 講者:林庭宇.
生成树.
鄧姚文 資料結構 第八章:圖(Graph) 鄧姚文
最短通路问题.
赵才荣 同济大学,电子与信息工程学院,智信馆410室
计算机问题求解 – 论题 图的连通度 2018年11月13日.
1757: Secret Chamber at Mount Rushmore
Konig 定理及其证明 杨欣然
All Sources Shortest Path The Floyd-Warshall Algorithm
Advanced Competitive Programming
An Optimal Minimum Spanning Tree Algorithm
Advanced Competitive Programming
Advanced Competitive Programming
圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Maximum Flow.
11506: Angry Programmer ★★★★☆ 題組:Contest Set Archive with Online Judge
Graph 1 Michael Tsai 2012/4/24 連載: 學生上課睡覺姿勢大全
计算机问题求解---论题3-12 图中的匹配与因子分解
JAVA 程式設計與資料結構 第二十一章 Graph.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Presentation transcript:

Elementary Graph Algorithms 本章內容將包含基本的圖形表示法,以及先深搜尋,先廣搜尋,拓樸排序,Strongly Connected Components。

Representations of graphs: undirected graph 無向圖G=(V,E),V代表點集合,E代表邊集合。E中的元素形式為集合{u,v},代表邊的兩端。 1 2 3 5 4 Adjacency-list及Adjacency-array在下頁有範例。 此兩種方法為比較常用的圖形表示法, 其中Adjacency-list比較適合表示邊比較稀疏的圖, 而Adjacency-array比較合適表示邊比較多的圖。 但是表示的方式不只這兩種,有時候為了提升搜尋速度, 也有使用其他更複雜的資料結構如Search tree或Hash table來儲存。 Elementary Graph Algorithms

Elementary Graph Algorithms Adjacency-list 可藉由Adjacency-list表示,將每個點相鄰的點集合用一個List存起來。 2 5 1 3 4 Elementary Graph Algorithms

Elementary Graph Algorithms Adjacency-array 可藉由Adjacency-array表示,利用一個二維陣列將每對點之間是否有邊連起來,有存1,沒有存0。 1 2 3 4 5 Elementary Graph Algorithms

Representations of graphs: Directed graph 有向圖G=(V,E),V代表點集合,E代表邊集合。E中的元素形式為(u,v),u代表起點,v代表中點。 1 2 3 5 4 Adjacency-list及Adjacency-array在下頁有範例。 Elementary Graph Algorithms

Elementary Graph Algorithms Adjacency-list 可藉由Adjacency-list表示,將每個點所指向的點集合存在List中。 2 5 3 4 1 Elementary Graph Algorithms

Elementary Graph Algorithms Adjacency-array 可藉由Adjacency-array表示,利用一個二維陣列A存,若(u,v)是一個邊則A[u][v]=1反之A[u][v]=0。 1 2 3 4 5 Elementary Graph Algorithms

Elementary Graph Algorithms Breadth-first search Breadth-first search(簡稱BFS,先廣搜尋)是最簡單的圖形搜尋演算法之一。 用於搜尋圖形G中,所有自點s開始出發,有路徑可以到達的點。 BFS利用Queue作為儲存將要探索的點的資料結構。 所謂的Breadth-first就是先探出最靠近s的點, 再由這些點探次靠近s的點,以此類推。 亦可用於找出Unweighted graph的最短路徑。 Elementary Graph Algorithms

Elementary Graph Algorithms Breadth-first search BFS是許多重要的圖形演算法的原型,如 Prim’s minimum spanning tree演算法以及Dijkstra’s single-source shortest-path演算法。 Elementary Graph Algorithms

Elementary Graph Algorithms BFS的運作範例 ∞ r s t u v w x y (a) Q 1 (b) 2 (c) 綠色,已經探索過的。 紅色,已經展開過的。 以s為探索起點。 節點上的數字代表跟s的最短距離。 Elementary Graph Algorithms

Elementary Graph Algorithms BFS的運作範例 r s t u Q 1 2 ∞ (d) t x v 2 2 2 2 1 2 ∞ v w x y r s t u Q 1 2 3 (e) x v u 2 2 3 2 1 2 ∞ v w x y r s t u Q 1 2 3 (f) v u y 2 3 3 2 1 2 3 v w x y Elementary Graph Algorithms

Elementary Graph Algorithms BFS的運作範例 r s t u Q 1 2 3 (g) u y 3 3 2 1 2 3 v w x y r s t u Q 1 2 3 (h) y 3 2 1 2 3 v w x y r s t u Q 1 2 3 (i) empty 2 1 2 3 v w x y Elementary Graph Algorithms

Elementary Graph Algorithms BFS演算法 起始點是s。 初始化時,將所有的點塗成白色。 已經發現的點,塗成綠色。 已經展開所有相鄰節點的點,塗成紅色。 u.d儲存s到u的距離。 u.π儲存自s到u的最短路徑中,u之前的一個點。 主要對照先前 Elementary Graph Algorithms

Elementary Graph Algorithms BFS(G,s) for each vertex u∈ G.V-{s} u.color = WHITE u.d = ∞ u.π = NIL s.color = GREEN s.d = 0 s.π = NIL Q = empty Enqueue(Q,s) while Q≠empty u = Dequeue(Q) for each v∈ G.Adj[u] if v.color == WHITE v.color = GREEN v.d = u.d + 1 v.π = u Enqueue(Q,v) u.color = RED Time Complexity: O(|E|+|V|) 第一個迴圈,初始化除s外所有的節點成白色,距離無限大,前一個點為空。 之後初始化s為綠色,距離0,前一個點是空。至此花去O(|V|) 接下來將s放入Q中,之後反覆執行Dequeue,直到Q空了為止。 每個Dequeue出來的點u,均將其白色的鄰居放入Q中, 並且將他們塗成綠色,距離設定成d[u]+1以及將前一個點設定為u。 處理完所有的鄰居之後,就將u塗成紅色。 因此每個點被放入Q一次,並且一個點被檢驗是不是白色的總次數為|E|, 故此部分花費O(|E|+|V|)的時間。 Elementary Graph Algorithms

Elementary Graph Algorithms BFS演算法的性質 執行過BFS之後,自s可達的點都被塗成紅色。 如v是s可達的點,則v.d代表s到v的最短路徑長。 如v是s可達的點,則(v.π, v)是某條自s到v最短路徑的一個邊。 v自s可達就是代表存在一個路徑,起點是s終點是v。 Elementary Graph Algorithms

Elementary Graph Algorithms BFS演算法的性質 邊集合T={(v.π,v): v自s可達}形成一個breadth-first tree。 1 2 3 r s t u v w x y 藍色的邊形成一個Breadth-first tree Elementary Graph Algorithms

Elementary Graph Algorithms Print path演算法 可在執行過BFS演算法的圖上印出s到v的最短路徑。如無路徑也會印出沒有路徑的訊息。 Print-Path(G,s,v) if v == s print s elseif v.π== NIL print “no path from” s “to” v else Print-Path(G,s,v.π) print v 此演算法利用BFS建立的表格π,並利用遞迴的方式, 利用之前提過的BFS性質, (π[v],v)是某一條最短路徑上的一邊, 找出一條path並且列印出來。 Elementary Graph Algorithms

Elementary Graph Algorithms Depth-first search Depth-first search(簡稱DFS,先深搜尋)是最簡單的圖形搜尋演算法之一。同樣用於搜尋圖形G中,所有自點s開始出發,有路徑可以到達的點。 DFS利用Stack作為儲存已經開始探索但尚未結束的點的資料結構。 相較於BFS,DFS可以利用程式語言的遞迴來避免自行實做資料結構。 Elementary Graph Algorithms

Elementary Graph Algorithms DFS演算法 起始點是s。 初始化時,將所有的點塗成白色。 點初次被發現的時候,塗成灰色。 點做完DFS-Visit的時候,塗成黑色。 u.d儲存u被發現的時間。 u.f儲存u做完DFS-Visit的時間。 u.d < u.f d[u]之所以必然比f[u]小是因為要先發現以後才能執行DFS-visit Elementary Graph Algorithms

Elementary Graph Algorithms DFS運作範例 發現時間 (a) u v w (b) u v w 1/ 1/ 2/ x y z x y z (c) u v w (d) u v w 1/ 2/ 1/ 2/ 飆上淺藍色的是Tree edge 3/ 4/ 3/ x y z x y z Elementary Graph Algorithms

Elementary Graph Algorithms DFS運作範例 (e) u v w (f) u v w 1/ 2/ 1/ 2/ B B 4/ 3/ 4/5 3/ x y z x y z (g) u v w (h) u v w 1/ 2/ 1/ 2/7 虛線+B的是代表Back edge B B 4/5 3/6 4/5 3/6 x y z x y z Elementary Graph Algorithms

Elementary Graph Algorithms DFS運作範例 (i) u v w (j) u v w 1/ 2/7 1/8 2/7 B F B F 4/5 3/6 4/5 3/6 x y z x y z (k) u v w (l) u v w 1/8 2/7 9/ 1/8 2/7 9/ B 虛線加上F的是Forward edge 虛線加上C的是Cross edge F B C F 4/5 3/6 4/5 3/6 x y z x y z Elementary Graph Algorithms

Elementary Graph Algorithms DFS運作範例 (m) u v w (n) u v w 1/8 2/7 9/ 1/8 2/7 9/ B C F B C F B 4/5 3/6 10/ 4/5 3/6 10/ x y z x y z (o) u v w (o) u v w 1/8 2/7 9/ 1/8 2/7 9/12 B C B C F F B B 4/5 3/6 10/11 4/5 3/6 10/11 x y z x y z Elementary Graph Algorithms

Elementary Graph Algorithms DFS演算法 DFS(G) for each vertex u∈ G.V do u.color = WHITE u.π = NIL time = 0 for each vertex u ∈ G.V if u.color == WHITE DFS-Visit(G,u) Elementary Graph Algorithms

Elementary Graph Algorithms DFS-Visit演算法 DFS-Visit(G, u) time = time+1 //u has just been discovered u.d = time u.color = GRAY for each v ∈ G.Adj[u] if v.color == WHITE v.π = u DFS-Visit(G, v) u.color = BLACK //DFS-Visit(G, u) is done time = time + 1 u.f = time Elementary Graph Algorithms

Elementary Graph Algorithms DFS的性質 DFS演算法的時間複雜度為O(|V|+|E|)。 執行過DFS演算法之後,所有的點都是黑色的。 {(v.π,v):v.π≠NIL}將形成一個Depth-first forest,也就是一個元素為Depth-first tree的集合。 如u到v之間在Depth-first forest中有一路徑,則稱u是v的ancestor,稱v是u的descendant。 時間複雜度由每個點執行過一次DFS-Visit而所有的DFS-Visit正巧把所有邊都瀏覽過一次。 Elementary Graph Algorithms

Elementary Graph Algorithms 邊的分類 假定邊為(u,v) Tree edges: 若初次發現v時是藉由(u,v),即v.π=u,則此邊稱作tree edge。 Back edges: 若v是u的ancestor,則此邊稱作back edge。 Forward edges: 若v是u的descendant且(u,v)不是tree edge,則此邊稱作forward edge。 Cross edges: 不屬於前三類的邊均稱為Cross edges。 下頁有範例,將一個圖進行DFS之後,所建成的Depth-first forest。 Elementary Graph Algorithms

Elementary Graph Algorithms 3/6 2/9 1/10 4/5 7/8 12/13 (a) y z s x w v B C 14/15 u 11/16 t F (b) s t z v u (a)是執行DFS之後的圖 (b)圖是表示Depth-first forest y w x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ( s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t) Elementary Graph Algorithms

Elementary Graph Algorithms (c) s C t B F z C u v B C y w 本圖中C是Cross edge B是Back edge F是Forward edge C x Elementary Graph Algorithms

Elementary Graph Algorithms Topological sort 對一DAG (Directed acyclic graph,有向無迴圈圖) G=(V,E),Topological sort(拓樸排序)是一對V的排序,其中若(u,v) ∈ E則在排序中u必須排在v之前。 常用於決定排程。 上面的圖是一個DAG。 下面則是此DAG對應的一個Topological sort。 上圖是一個穿衣服的優先順序,穿內褲(undershorts)之後才能穿長褲(pants), 穿襪子(socks)之後才能穿鞋子(shoes)等等。 Elementary Graph Algorithms

Elementary Graph Algorithms 一個表示穿衣服先後順序的圖 內褲 襪子 長褲 鞋子 皮帶 襯衫 領帶 夾克 手錶 經拓樸排序後,可依此順序穿上所有衣物。 襪子 內褲 長褲 鞋子 手錶 襯衫 皮帶 領帶 夾克 Elementary Graph Algorithms

Elementary Graph Algorithms Topological sort演算法 利用DFS演算法,計算出每一個點u的Finish time (u.f)。 當一個點執行完畢DFS-Visit時,將該點放入一公用的Linked List前端。 最後此Linked List存放的順序即為一Topological sort。 Elementary Graph Algorithms

Topological sort操作範例 每個點旁的數字代表Discovery time/Finish Time 內褲 襪子 長褲 鞋子 皮帶 襯衫 領帶 夾克 手錶 11/16 12/15 6/7 1/8 2/5 3/4 17/18 13/14 9/10 每個點旁的數字代表Discovery time/Finish Time 襪子 內褲 長褲 鞋子 手錶 襯衫 皮帶 領帶 夾克 11/16 12/15 6/7 1/8 3/4 13/14 17/18 9/10 2/5 以上為公用的Linked List在執行完DFS之後的順序。

Elementary Graph Algorithms Lemma 22.11: A directed graph G is acyclic iff DFS(G) yields no back edges. Pf:  Suppose there is a back edge (u,v), v is an ancestor of u. Thus there is a path from v to u and a cycle exists.  Suppose G has a cycle c. We show DFS(G) yields a back edge. Let v be the first vertex to be discovered in c, and (u,v) be the preceding edge in c. At time v.d, there is a path of white vertices from v to u. By the white-path thm., u becomes a descendant of v in the DF forest. Thus (u,v)is a back edge. Elementary Graph Algorithms

Elementary Graph Algorithms TOPOLOGICAL-SORT(G) produces a topological sort of G pf: Suppose DFS is run to determinate finishing times for vertices. It suffices to show that for any pair of u,v , if there is an edge from u to v, then v.f < u.f. When (u,v) is explored by DFS(G), v cannot be gray. Therefore v must be either white or black. 1. If v is white, it becomes a descendant of u, so v.f<u.f 2. If v is black, then v.f<u.f Elementary Graph Algorithms

Strongly connected components 對一個有向圖G=(V,E)而言,一個Strongly Connected Component C是一個滿足下列條件的點集合: C⊆V 對任C中相異兩點u及v,存在一條路徑由u到v且有另一路徑由v到u。 Elementary Graph Algorithms

Elementary Graph Algorithms

Strongly connected components演算法 呼叫DFS(G)對所有點u,計算出u.f,即finishing time。 計算出GT,即點集合與G相同,而邊連接方向相反的圖。 呼叫DFS(GT),但在DFS主迴圈中,選擇點的順序是先挑取u.f值較大的點u。(即以u.f遞減順序挑取。) 在DFS(GT)的Depth-first forest中,每一個樹均是一個Strongly connected component。 Elementary Graph Algorithms

G: GT: 13/14 11/16 12/15 3/4 1/10 2/7 8/9 5/6 a b c d e f g h abe cd h

Elementary Graph Algorithms Lemma 22.13 : Let C and C’ be distinct strongly connected components in directed graph G=(V, E), let u, v in C and u’, v’ in C’, and suppose there is a path from u to u’ in G. Then there cannot also be a path from v’ to v in G. Def: Let U  V, define d(U) = min u U { u.d } f (U) = max u U { u.f } Elementary Graph Algorithms

Elementary Graph Algorithms Lemma 22.14 Let C and C’ be distinct strongly connected components in directed graph G=(V, E). Suppose that there is an edge (u, v) in E, where u in C and v in C’. Then f (C) > f ( C’). pf: Case (1): If d(C) < d(C’): let x be the 1st discovered vertex in C. At time x.d all vertices in C and C’ are white. There is a path from x to all (white) vertices in C and to all vertices in C’: x~↝ u  v ~↝ w. All vertices in C and C’ are descendants of x. Thus x.f = f (C) > f(C’). Elementary Graph Algorithms

Elementary Graph Algorithms Lemma 22.14 Let C and C’ be distinct strongly connected components in directed graph G=(V, E). Suppose that there is an edge (u, v) in E, where u in C and v in C’. Then f (C) > f ( C’). pf: Case (2): If d(C) > d(C’): let y be the 1st discovered vertex in C’. At time y.d all vertices in C’ are white and there is a path from y to all vertices in C’. I.e. all vertices in C’ are descendants of y. So y.f = f(C’). There cannot be a path from C’ to C. Why? Thus any w in C has w.f > y.f and so f(C) > f(C’). Elementary Graph Algorithms

Elementary Graph Algorithms Corollary 22.15: Let C and C’ be distinct strongly connected components in directed graph G=(V, E). Suppose that there is an edge (u, v) in ET, where u in C and v in C’. Then f ( C ) < f ( C’ ). Pf: It is clear that (v, u) is in E. By the previous lemma we have f( C’ ) > f ( C ). Elementary Graph Algorithms

Elementary Graph Algorithms Theorem 22.16 Strongly-Connected-Component(G) correctly computes the strongly connected components of a directed graph. pf: By induction on the number (k) of depth-first trees found in the DFS of GT, where each tree forms a strongly connected component. Basis: trivial for k=0. Inductive step: assume each of the first k DFS trees produced in line 3 is a SCC. Consider the (k+1)-st tree produced. Let u be the root of this tree and let u be in SCC C. Thus u.f = f ( C ) > f ( C’ ) for any other SCC C’ yet to be visited. Note we visit in decreasing finishing time. Elementary Graph Algorithms

Elementary Graph Algorithms All other vertices in C are descendant of u in its DFS. By inductive hypothesis and the Corollary 15 any edges in GT that leave C must be to SCC’s already visited. Thus, no vertex in any SCC other than C will be a descendant of u during the DFS of GT. Thus, the vertices of the DFS tree in GT that is rooted at u form exactly one SCC.  Elementary Graph Algorithms