Elementary Graph Algorithms

Presentation on theme: "Elementary Graph Algorithms"— Presentation transcript:

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

2 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

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

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

5 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

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

7 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

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

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

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

11 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

12 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

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

14 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

15 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

16 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

17 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

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

19 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

20 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

21 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

22 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

23 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

24 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

25 Elementary Graph Algorithms
DFS-Visit演算法 DFS-Visit(G, u) time = time //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

26 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

27 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

28 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 ( s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t) Elementary Graph Algorithms

29 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

30 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

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

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

33 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之後的順序。

34 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

35 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

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

37 Elementary Graph Algorithms

38 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

39 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

40 Elementary Graph Algorithms
Lemma : 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

41 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

42 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

43 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

44 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

45 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