《主题Graph表示法与DFS.ppt》由会员分享，可在线阅读，更多相关《主题Graph表示法与DFS.ppt（44页珍藏版）》请在三一文库上搜索。
1、1,主題: Graph:表示法與 DFS,解題技巧 基本定義 Graph 表示法 (存法) DFS and applications 例題講解 歷年題目,2,基本定義,Graph 由 vertices 和 edges 所組成,3,基本定義,undirected V.S directed 定義在 edge 上 undirected edge edge 沒有方向性，如果說 a 和 b 之間有一條 edge，則表示 a 可經由這條 edge 到 b，b 也可由這條 edge 到 a directed edge edge 有方向性，比如說 a 到 b 有一條 edge，則表示 a 可經由這條 edge
2、 到 b，但是 b 不能由這條 edge 到 a,4,undirected,directed,Example,5,基本定義,unweighted V.S weighted 可定義在 vertex 上或是 edge 上 edge 的 weight 用來表示這個 edge 長度或其它定義的 weight，比如說經過這條 edge 所要花費的 cost 如果是 unweighted edge，一般來說 edge 的長度就是等於 1 vertex 的 weight 用來表示這個 vertex 的重要性或其它定義的 weight，比如說經過這個 vertex 所要花費的 cost 如果是 unweigh
3、ted vertex，一般來說 vertex 的 weight 就是等於 1,6,基本定義,degree 定義在 vertex 上 undirected graph vertex 的 degree 就等於跟這個 vertex 相連的 edge 個數 directed graph vertex 的 degree 分成兩種 indegree 所有指向這個 vertex 的 edge 個數 outdegree 所有由這個 vertex 指出去的 edge 個數,7,undirected,directed,Example,8,建議,當看到一個題目時，如果是 graph 上的題目或是要轉成 graph
4、來做的題目的話，首先要判斷這個 graph 是 directed 或 undirected，是 weighted 或 unweighted，是不是一些比較特殊的 graph，因為所要存的資料，適用的演算法，解題技巧都不太一樣,9,Graph 表示法 (存法),Adjacency-matrix 開一個二維陣列，size 是 n n n 為 vertices 的個數 unweighted-edge: Ai, j = 1 代表由 vertex i 到 vertex j 有一條 edge，Ai, j = 0 代表沒有 weighted-edge: Ai, j 存由 vertex i 到 vertex
5、j 這條 edge 的 weight ( 表示這條 edge 不存在) Adjacency-list 開 n 個 list，總共的 size 是 n + m m 為 edge 的個數 每個 list 後面接著跟這個 vertex 可連到的 vertex,10,Example: undirected,0,1,4,3,2,0 1 2 3 4 0 0 1 0 0 1 1 1 0 1 1 1 2 0 1 0 1 0 3 0 1 1 0 1 4 1 1 0 1 0,adjacency-matrix,0,1,2,3,4,1,0,1,1,3,4,4,3,4,0,/,/,2,2,1,/,/,3,/,adjac
6、ency-list,11,-1 表示 nil 有 edge length 時使用另一個陣列 len2m,Adjacency-list 存法,0,1,4,3,2,0,1,3,3,4,1,0,1,1,3,4,4,3,4,0,/,/,2,2,1,/,/,3,/,8,1,2,4,10,2,-1,12,0,1,4,3,2,0 1 2 3 4 0 0 1 0 0 1 1 0 0 1 0 1 2 0 0 0 1 0 3 0 1 0 0 0 4 0 0 0 1 0,adjacency-matrix,0,1,2,3,4,1,2,3,1,3,/,/,/,4,4,/,/,adjacency-list,Example
7、: directed,13,Graph 存法,建議用 adjacency-matrix 方便，好寫 可直接查表知道 vertex i 和 vertex j 之間相連的情況 (用 adjacency-list 的話需要 scan list 一次) 雖然較花 memory 和時間，不過絕大部分的題目用 adjacency-matrix 就夠了,14,常見的 input 給法 (I),給一堆 edge 1 3 2 5 1 5 5 4 2 3 4 2 3 4 每次讀進一條 edge 之後，就把它加入 adjacency-matrix 之中，記得要看清楚題目的 edge 有沒有方向性，如果是 undir
8、ected 的 edge，要記得雙向 edge 都要加 比如讀到 1 3 這條 edge，而且是 undirected，就表示 1 到 3 和 3 到 1 都有 edge,15,常見的 input 給法 (II),直接給 adjacency-list 或 adjacency-matrix 2 5 0 1 0 0 1 1 5 3 4 1 0 1 1 1 2 4 或 0 1 0 1 0 2 5 3 0 1 1 0 1 4 1 2 1 1 0 1 0 直接讀進來存進 adjacency-matrix 中就好,16,常見的 input 給法 (III),給法跟前面兩種很像，只是 vertex 的編號可
9、能很大，而不是 1 到 n，或是 vertex 的編號不是數字 1 100000 abc def 100000 33333 或 def eas 33333 1 eas abc 不可能有機會讀到多大的數字就開多大的二維陣列 也沒辦法用英文字做陣列的 index,17,解決方法,需要做 re-label 的動作 把 1 = 0, 33333 = 1, 100000 = 2, 把 abc = 0, def = 1, eas = 2, 因為只出現三種數字，所以只要開一個 3 3的二維陣列，再加上一個用來做 mapping 的表就好,18,1,33333,100000,0,1,2,原來的數字,re-la
10、bel 後的數字,0,1,1,1,0,1,1,1,0,Example,adjacency-matrix,19,解決方法,要是 vertex 的個數不少，每次如果要去查 mapping 的表時，如果都做 linear search 時間可能會花蠻多 在做 re-label 的時候，可以先 sort 好之後再做 mapping 的動作，這樣之後要去查表的時侯就可以用 binary search 來查，可以省一些時間 先讀進所有 input 存起來 sort 後造表 最後再建 adjacency-matrix,20,DFS and applications,Depth-first search (D
11、FS) Connected component Strongly connected component Topological sort,21,Depth-first search (DFS),如同名字一樣，是一種以深度 (depth) 為優先 (first) 所做的 traversal (search) 在暴力法，tree traversal 上都有相類似的概念,22,DFS on graph,任挑一個 vertex v 當起點，從 adjv 中挑一個沒走過的 vertex 往下走，因為要以深度為優先，所以走到下一個 vertex 之後，就再看看能不能繼續往下走到一個沒走過的 vertex
12、 ，如果可以的話就往下走，不行的話就回頭看看之前還有沒有別條路可以走 當走到都沒有路可走的時侯，就看看是不是還有沒被走到的 vertex，有的話就再挑一個點起點，繼續做 traversal 的動作 走過的 vertex 不要重覆走 要記錄 vertex 有沒有被走過,23,Example,24,Data structure for DFS,visit 陣列 記錄 vertex 是否被走過 start 陣列 記錄 vertex 在第幾步的時侯第一次被看到 finish 陣列 記錄 vertex 在第幾步的時侯發現無路可走，要回到前一個 vertex 上,25,Example,1/,2/,3/,4
13、/,9/,10/,4/5,3/6,2/7,1/8,10/11,9/12,26,Pseudo code,DFS (G) for each vertex v VG visitv = 0; time = 0; for each vertex v VG if (visitv = 0) DFS_visit(v); ,27,Pseudo code,DFS_visit(v) time = time + 1; startv = time; for each u adjv if (visitu = 0) DFS_visit(u); time = time + 1; finishv = time; ,scan a
14、djacency-matrix for (i = 0; i n; i+) if (adjvi = 1),28,Summary: DFS,DFS 只是一種概念，該怎麼用其實主要看題目而定 start 和 finish time 也不一定會用到，如果題目沒有需要的話也可以省略,29,Connected component,對 undirected graph 來說，給一堆 vertices，如果這裡面任兩個 vertices 都可以走到對方的話，那這一堆 vertices 就屬於同一個 connected component 如果是 directed graph，則稱作 strongly conn
15、ected component,30,例題講解: A. 459 http:/acm.uva.es/p/v4/459.html,給一個 undirected graph，vertex 是由 A 到 Z 來編號 input 給法是給所有的 edge 試問: 這個 undirected graph 中共有幾個 connected component,31,Sample input/output,Sample input 1 E AB CE DB EC Sample output 2,vertex 編號最大會到 E,32,Sample,A,D,B,C,E,共兩個 connected component
16、,33,解法,找一個還沒被找過的點，由它開始做 DFS，所有能到達的點都是屬於同一個 connected component 當沒有路可以走的時侯，就找看看還有沒有沒被走過的點，有的話就從它開始做 DFS，這些點則屬於另一個 connected component,34,因為是 undirected graph，edge 沒有方向性，所以讀進一條 edge 時要記得兩個方向的 edge 都要存 這個題目不需要 start 和 finish time,35,Strongly connected component,對 directed graph 來說，給一堆 vertices，如果這裡面任兩個
17、 vertices 都有 directed path的話，就屬於同一個 strongly connected component,36,Example,a,b,c,d,e,f,g,h,共有四個 strongly connected component,37,做法,先做一次 DFS，並記住 finish time 將所有的 edge 反向 原本 A 到 B 的 edge 要變成 B 到 A 的 edge 再做一次 DFS，但是這次在挑選由誰開始做 DFS 的時侯是以第一次 finish time 較大的開始挑 當做第二次 DFS 時，每次由一個 vertex 出發所能走的到的人都屬於同一個 st
18、rongly connected component,38,Example,a,b,c,d,e,f,g,h,a,b,c,d,e,f,g,h,39,Topological sort (拓蹼排序),例題 有個人早上起床時要開始穿戴衣物，請你來幫他決定該怎麼穿戴 要穿戴的東西 手錶，襪子，鞋子，內衣褲，褲子，上衣，外套 有一些東西的穿法是有必然的先後順序 先穿襪子才能穿鞋子 先穿內衣褲才能穿褲子，上衣 穿了上衣才能穿外套 Topological sort: 決定一個可行的穿戴順序,40,褲子,上衣,外套,手錶,內衣褲,襪子,鞋子,41,Topological sort: 做法,做 DFS，並且記錄每
19、個 vertex 的 finish time 只要依照 finish time 從大到小排好順序就可以了 implement 用一個 stack S，每次有 vertex 結束就 push 進 S，不必記 finish time DFS 結束，由 S 一個一個 pop 出來輸出,42,Example,褲子,上衣,外套,手錶,內衣褲,襪子,鞋子,43,注意,Topological sort 必須在 directed acyclic graph (DAG) 之下才能做 acyclic: 沒有 cycle 如果有 cycle 的話 A 要在 B 之前做，B 要在 C 之前做，C 要在 A 之前做，這
20、樣根本就沒辦法排,44,歷年題目,練習題 A. 459 Graph Connectivity http:/acm.uva.es/p/v4/459.html A. 315 Network http:/acm.uva.es/p/v3/315.html A. 599 The forest for the Trees http:/acm.uva.es/p/v5/599.html A. 200 Rare Order http:/acm.uva.es/p/v2/200.html 挑戰題 A. 10418 Hyper Toy Soldiers http:/acm.uva.es/p/v104/10418.html 其它歷年題目 H.91.1, H.91.6, H.90.1, H.89.2, H.89.3, H.88.2, H.88.3,