《主题Graph表示法与DFS》由会员分享，可在线阅读，更多相关《主题Graph表示法与DFS（44页珍藏版）》请在金锄头文库上搜索。
1、主题Graph表示法与DFSStillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望基本定義nGraphn由 vertices 和 edges 所組成2基本定義nundirected V.S directedn定義在 edge 上nundirected edgenedge 沒有方向性，如果說 a 和 b 之間有一條 edge，則表示 a 可經由這條 edge 到 b，b 也可由這條 edge 到 andirected edgenedge 有方向性，比如說 a 到 b 有一條 edge，則表示
2、 a 可經由這條 edge 到 b，但是 b 不能由這條 edge 到 a3undirecteddirectedExample4基本定義nunweighted V.S weightedn可定義在 vertex 上或是 edge 上nedge 的 weightn用來表示這個 edge 長度或其它定義的 weight，比如說經過這條 edge 所要花費的 costn如果是 unweighted edge，一般來說 edge 的長度就是等於 1nvertex 的 weightn用來表示這個 vertex 的重要性或其它定義的 weight，比如說經過這個 vertex 所要花費的 costn如果是
3、unweighted vertex，一般來說 vertex 的 weight 就是等於 15基本定義ndegreen定義在 vertex 上nundirected graphnvertex 的 degree 就等於跟這個 vertex 相連的 edge 個數ndirected graphnvertex 的 degree 分成兩種nindegreen所有指向這個 vertex 的 edge 個數noutdegreen所有由這個 vertex 指出去的 edge 個數6undirecteddirecteddegree = 3indegree = 2outdegree = 2Example7建議n當
4、看到一個題目時，如果是 graph 上的題目或是要轉成 graph 來做的題目的話，首先要判斷這個 graph 是 directed 或 undirected，是 weighted 或 unweighted，是不是一些比較特殊的 graph，因為所要存的資料，適用的演算法，解題技巧都不太一樣8Graph 表示法 (存法)nAdjacency-matrixn開一個二維陣列，size 是 n nnn 為 vertices 的個數nunweighted-edge: Ai, j = 1 代表由 vertex i 到 vertex j 有一條 edge，Ai, j = 0 代表沒有nweighted-e
5、dge: Ai, j 存由 vertex i 到 vertex j 這條 edge 的 weight ( 表示這條 edge 不存在)nAdjacency-listn開 n 個 list，總共的 size 是 n + mnm 為 edge 的個數n每個 list 後面接著跟這個 vertex 可連到的 vertex9Example: undirected01432 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 0adjacency-matrix012341011344340/221/3/adjacency-list
6、10 -1 表示 nil 有 edge length 時使用另一個陣列 len2mAdjacency-list 存法01432013341011344340/221/3/i012345678910111213adjn096811node2m14442313102301next2m1-11045-17-123-11213-18124102-11101432 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 0adjacency-matrix0123412313/44/adjacency-listExample: dir
7、ected12Graph 存法n建議用 adjacency-matrixn方便，好寫n可直接查表知道 vertex i 和 vertex j 之間相連的情況 (用 adjacency-list 的話需要 scan list 一次)n雖然較花 memory 和時間，不過絕大部分的題目用 adjacency-matrix 就夠了13常見的 input 給法 (I)n給一堆 edge1 32 51 55 42 34 23 4n每次讀進一條 edge 之後，就把它加入 adjacency-matrix 之中，記得要看清楚題目的 edge 有沒有方向性，如果是 undirected 的 edge，要記得
8、雙向 edge 都要加n比如讀到 1 3 這條 edge，而且是 undirected，就表示 1 到 3 和 3 到 1 都有 edge14常見的 input 給法 (II)n直接給 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 0n直接讀進來存進 adjacency-matrix 中就好15常見的 input 給法 (III)n給法跟前面兩種很像，只是 vertex 的編號可能很大，而不是 1 到 n，或是 vertex 的編號不是數字
9、1 100000abc def100000 33333或def eas33333 1eas abcn不可能有機會讀到多大的數字就開多大的二維陣列n也沒辦法用英文字做陣列的 index16解決方法n需要做 re-label 的動作n把 1 = 0, 33333 = 1, 100000 = 2, n把 abc = 0, def = 1, eas = 2, n因為只出現三種數字，所以只要開一個 3 3的二維陣列，再加上一個用來做 mapping 的表就好17133333 100000012原來的數字re-label 後的數字011101110Exampleadjacency-matrix18解決方法
10、n要是 vertex 的個數不少，每次如果要去查 mapping 的表時，如果都做 linear search 時間可能會花蠻多n在做 re-label 的時候，可以先 sort 好之後再做 mapping 的動作，這樣之後要去查表的時侯就可以用 binary search 來查，可以省一些時間n先讀進所有 input 存起來nsort 後造表n最後再建 adjacency-matrix19DFS and applicationsnDepth-first search (DFS)nConnected componentnStrongly connected componentnTopologi
11、cal sort20Depth-first search (DFS)n如同名字一樣，是一種以深度 (depth) 為優先 (first) 所做的 traversal (search)n在暴力法，tree traversal 上都有相類似的概念21DFS on graphn任挑一個 vertex v 當起點，從 adjv 中挑一個沒走過的 vertex 往下走，因為要以深度為優先，所以走到下一個 vertex 之後，就再看看能不能繼續往下走到一個沒走過的 vertex ，如果可以的話就往下走，不行的話就回頭看看之前還有沒有別條路可以走n當走到都沒有路可走的時侯，就看看是不是還有沒被走到的 ver
12、tex，有的話就再挑一個點起點，繼續做 traversal 的動作n走過的 vertex 不要重覆走n要記錄 vertex 有沒有被走過22Example23Data structure for DFSnvisit 陣列n記錄 vertex 是否被走過nstart 陣列n記錄 vertex 在第幾步的時侯第一次被看到nfinish 陣列n記錄 vertex 在第幾步的時侯發現無路可走，要回到前一個 vertex 上24Example1/2/3/4/9/10/4/53/62/71/810/119/1225Pseudo codeDFS (G) for each vertex v VGvisitv
13、= 0;time = 0;for each vertex v VGif (visitv = 0)DFS_visit(v);26Pseudo codeDFS_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)27Summary: DFSnDFS 只是一種概念，該怎麼用其實主要看題目而定nstart 和 finis
14、h time 也不一定會用到，如果題目沒有需要的話也可以省略28Connected componentn對 undirected graph 來說，給一堆 vertices，如果這裡面任兩個 vertices 都可以走到對方的話，那這一堆 vertices 就屬於同一個 connected componentn如果是 directed graph，則稱作 strongly connected component29例題講解: A. 459http:/acm.uva.es/p/v4/459.htmln給一個 undirected graph，vertex 是由 A 到 Z 來編號ninput 給
15、法是給所有的 edgen試問: 這個 undirected graph 中共有幾個 connected component30Sample input/outputSample input1EABCEDBECSample output2vertex 編號最大會到 E31SampleADBCE共兩個 connected component32解法n找一個還沒被找過的點，由它開始做 DFS，所有能到達的點都是屬於同一個 connected componentn當沒有路可以走的時侯，就找看看還有沒有沒被走過的點，有的話就從它開始做 DFS，這些點則屬於另一個 connected component3
16、3n因為是 undirected graph，edge 沒有方向性，所以讀進一條 edge 時要記得兩個方向的 edge 都要存n這個題目不需要 start 和 finish time34Strongly connected componentn對 directed graph 來說，給一堆 vertices，如果這裡面任兩個 vertices 都有 directed path的話，就屬於同一個 strongly connected component35Exampleabcdefgh共有四個 strongly connected component36做法n先做一次 DFS，並記住 fini
17、sh time n將所有的 edge 反向n原本 A 到 B 的 edge 要變成 B 到 A 的 edgen再做一次 DFS，但是這次在挑選由誰開始做 DFS 的時侯是以第一次 finish time 較大的開始挑n當做第二次 DFS 時，每次由一個 vertex 出發所能走的到的人都屬於同一個 strongly connected component37Exampleabcdefgh13/1411/161/108/912/153/42/75/6abcdefgh38Topological sort (拓蹼排序)n例題n有個人早上起床時要開始穿戴衣物，請你來幫他決定該怎麼穿戴n要穿戴的東西n手
18、錶，襪子，鞋子，內衣褲，褲子，上衣，外套n有一些東西的穿法是有必然的先後順序n先穿襪子才能穿鞋子n先穿內衣褲才能穿褲子，上衣n穿了上衣才能穿外套nTopological sort: 決定一個可行的穿戴順序39褲子上衣外套手錶內衣褲襪子鞋子內衣褲褲子上衣襪子外套鞋子手錶手錶襪子鞋子內衣褲上衣外套褲子40Topological sort: 做法n做 DFS，並且記錄每個 vertex 的 finish time n只要依照 finish time 從大到小排好順序就可以了nimplementn用一個 stack S，每次有 vertex 結束就 push 進 S，不必記 finish timenD
19、FS 結束，由 S 一個一個 pop 出來輸出41Example褲子上衣外套手錶內衣褲襪子鞋子1/82/34/75/69/1210/1113/14手錶襪子鞋子內衣褲上衣外套褲子finish time141211876342注意nTopological sort 必須在 directed acyclic graph (DAG) 之下才能做nacyclic: 沒有 cyclen如果有 cycle 的話nA 要在 B 之前做，B 要在 C 之前做，C 要在 A 之前做，這樣根本就沒辦法排43歷年題目n練習題nA. 459 Graph Connectivitynhttp:/acm.uva.es/p/v
20、4/459.htmlnA. 315 Networknhttp:/acm.uva.es/p/v3/315.htmlnA. 599 The forest for the Treesnhttp:/acm.uva.es/p/v5/599.htmlnA. 200 Rare Order nhttp:/acm.uva.es/p/v2/200.htmln挑戰題nA. 10418 Hyper Toy Soldiersnhttp:/acm.uva.es/p/v104/10418.htmln其它歷年題目nH.91.1, H.91.6, H.90.1, H.89.2, H.89.3, H.88.2, H.88.344
