《主题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 edgeedge 沒有方向性，如果說 a 和 b 之間有一條 edge，則表示 a 可經由這條 edge 到 b，b 也可由這條 edge 到 adirected edgeedge 有方向性，比如說 a 到 b 有一條 edge，則表示 a 可經由這條 edge 到 b，但是 b 不能
2、由這條 edge 到 a,4,undirected,directed,Example,5,基本定義,unweighted V.S weighted可定義在 vertex 上或是 edge 上edge 的 weight用來表示這個 edge 長度或其它定義的 weight，比如說經過這條 edge 所要花費的 cost如果是 unweighted edge，一般來說 edge 的長度就是等於 1vertex 的 weight用來表示這個 vertex 的重要性或其它定義的 weight，比如說經過這個 vertex 所要花費的 cost如果是 unweighted vertex，一般來說 ver
3、tex 的 weight 就是等於 1,6,基本定義,degree定義在 vertex 上undirected graphvertex 的 degree 就等於跟這個 vertex 相連的 edge 個數directed graphvertex 的 degree 分成兩種indegree所有指向這個 vertex 的 edge 個數outdegree所有由這個 vertex 指出去的 edge 個數,7,undirected,directed,Example,8,建議,當看到一個題目時，如果是 graph 上的題目或是要轉成 graph 來做的題目的話，首先要判斷這個 graph 是 dire
4、cted 或 undirected，是 weighted 或 unweighted，是不是一些比較特殊的 graph，因為所要存的資料，適用的演算法，解題技巧都不太一樣,9,Graph 表示法(存法),Adjacency-matrix開一個二維陣列，size 是 n nn 為 vertices 的個數unweighted-edge:Ai,j=1 代表由 vertex i 到 vertex j 有一條 edge，Ai,j=0 代表沒有weighted-edge:Ai,j 存由 vertex i 到 vertex j 這條 edge 的 weight(表示這條 edge 不存在)Adjacency
5、-list開 n 個 list，總共的 size 是 n+mm 為 edge 的個數每個 list 後面接著跟這個 vertex 可連到的 vertex,10,Example:undirected,0,1,4,3,2,0 1 2 3 40 0 1 0 0 11 1 0 1 1 12 0 1 0 1 03 0 1 1 0 14 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,/,adjacency-list,11,-1 表示 nil 有 edge length 時使用另一個陣列 len2m,Adja
6、cency-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 11 0 0 1 0 12 0 0 0 1 03 0 1 0 0 04 0 0 0 1 0,adjacency-matrix,0,1,2,3,4,1,2,3,1,3,/,/,/,4,4,/,/,adjacency-list,Example:directed,13,Graph 存法,建議用 adjacency-matrix方便，好寫可直接查表知道 verte
7、x i 和 vertex j 之間相連的情況(用 adjacency-list 的話需要 scan list 一次)雖然較花 memory 和時間，不過絕大部分的題目用 adjacency-matrix 就夠了,14,常見的 input 給法(I),給一堆 edge1 32 51 55 42 34 23 4每次讀進一條 edge 之後，就把它加入 adjacency-matrix 之中，記得要看清楚題目的 edge 有沒有方向性，如果是 undirected 的 edge，要記得雙向 edge 都要加比如讀到 1 3 這條 edge，而且是 undirected，就表示 1 到 3 和 3 到
8、 1 都有 edge,15,常見的 input 給法(II),直接給 adjacency-list 或 adjacency-matrix2 50 1 0 0 11 5 3 41 0 1 1 12 4或0 1 0 1 02 5 30 1 1 0 14 1 21 1 0 1 0直接讀進來存進 adjacency-matrix 中就好,16,常見的 input 給法(III),給法跟前面兩種很像，只是 vertex 的編號可能很大，而不是 1 到 n，或是 vertex 的編號不是數字1 100000abc def100000 33333或def eas33333 1eas abc不可能有機會讀到多
9、大的數字就開多大的二維陣列也沒辦法用英文字做陣列的 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-label 後的數字,0,1,1,1,0,1,1,1,0,Example,adjacency-matrix,19,解決方法,要是 vertex 的個數不少，每次如果要去查 mapping 的表時，如果都做 linear search 時間
10、可能會花蠻多在做 re-label 的時候，可以先 sort 好之後再做 mapping 的動作，這樣之後要去查表的時侯就可以用 binary search 來查，可以省一些時間先讀進所有 input 存起來sort 後造表最後再建 adjacency-matrix,20,DFS and applications,Depth-first search(DFS)Connected componentStrongly connected componentTopological sort,21,Depth-first search(DFS),如同名字一樣，是一種以深度(depth)為優先(firs
11、t)所做的 traversal(search)在暴力法，tree traversal 上都有相類似的概念,22,DFS on graph,任挑一個 vertex v 當起點，從 adjv 中挑一個沒走過的 vertex 往下走，因為要以深度為優先，所以走到下一個 vertex 之後，就再看看能不能繼續往下走到一個沒走過的 vertex，如果可以的話就往下走，不行的話就回頭看看之前還有沒有別條路可以走當走到都沒有路可走的時侯，就看看是不是還有沒被走到的 vertex，有的話就再挑一個點起點，繼續做 traversal 的動作走過的 vertex 不要重覆走要記錄 vertex 有沒有被走過,23
12、,Example,24,Data structure for DFS,visit 陣列記錄 vertex 是否被走過start 陣列記錄 vertex 在第幾步的時侯第一次被看到finish 陣列記錄 vertex 在第幾步的時侯發現無路可走，要回到前一個 vertex 上,25,Example,1/,2/,3/,4/,9/,10/,4/5,3/6,2/7,1/8,10/11,9/12,26,Pseudo code,DFS(G)for each vertex v VGvisitv=0;time=0;for each vertex v VGif(visitv=0)DFS_visit(v);,27
13、,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 adjacency-matrixfor(i=0;i n;i+)if(adjvi=1),28,Summary:DFS,DFS 只是一種概念，該怎麼用其實主要看題目而定start 和 finish time 也不一定會用到，如果題目沒有需要的話也可以省略,29,Connected component,對 undirected graph 來說，給一堆 vert
14、ices，如果這裡面任兩個 vertices 都可以走到對方的話，那這一堆 vertices 就屬於同一個 connected component如果是 directed graph，則稱作 strongly connected component,30,例題講解:A.459,給一個 undirected graph，vertex 是由 A 到 Z 來編號input 給法是給所有的 edge試問:這個 undirected graph 中共有幾個 connected component,31,Sample input/output,Sample input1EABCEDBECSample ou
15、tput2,vertex 編號最大會到 E,32,Sample,A,D,B,C,E,共兩個 connected component,33,解法,找一個還沒被找過的點，由它開始做 DFS，所有能到達的點都是屬於同一個 connected component當沒有路可以走的時侯，就找看看還有沒有沒被走過的點，有的話就從它開始做 DFS，這些點則屬於另一個 connected component,34,因為是 undirected graph，edge 沒有方向性，所以讀進一條 edge 時要記得兩個方向的 edge 都要存這個題目不需要 start 和 finish time,35,Strongl
16、y connected component,對 directed graph 來說，給一堆 vertices，如果這裡面任兩個 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 的時侯是以第一次 f
17、inish time 較大的開始挑當做第二次 DFS 時，每次由一個 vertex 出發所能走的到的人都屬於同一個 strongly 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,褲子,上衣,外
18、套,手錶,內衣褲,襪子,鞋子,41,Topological sort:做法,做 DFS，並且記錄每個 vertex 的 finish time 只要依照 finish time 從大到小排好順序就可以了implement用一個 stack S，每次有 vertex 結束就 push 進 S，不必記 finish timeDFS 結束，由 S 一個一個 pop 出來輸出,42,Example,褲子,上衣,外套,手錶,內衣褲,襪子,鞋子,43,注意,Topological sort 必須在 directed acyclic graph(DAG)之下才能做acyclic:沒有 cycle如果有 cycle 的話A 要在 B 之前做，B 要在 C 之前做，C 要在 A 之前做，這樣根本就沒辦法排,44,歷年題目,練習題A.459 Graph ConnectivityA.315 NetworkA.599 The forest for the TreesA.200 Rare Order 挑戰題A.10418 Hyper Toy Soldiers其它歷年題目,
