《主题graph表示法与dfs》由会员分享，可在线阅读，更多相关《主题graph表示法与dfs（44页珍藏版）》请在金锄头文库上搜索。
1、主題: Graph:表示法與 DFSn解題技巧n基本定義nGraph 表示法 (存法)nDFS and applications n例題講解n歷年題目1基本定義nGraphn由 vertices 和 edges 所組成2基本定義nundirected V.S directedn定義在 edge 上nundirected edgenedge 沒有方向性，如果說 a 和 b 之間有一條 edge，則表示 a 可經由這條 edge 到 b，b 也可由這條 edge 到 andirected edgenedge 有方向性，比如說 a 到 b 有一條 edge，則表示 a 可經 由這條 edge 到 b
2、，但是 b 不能由這條 edge 到 a3undirecteddirectedExample4基本定義nunweighted V.S weightedn可定義在 vertex 上或是 edge 上nedge 的 weightn用來表示這個 edge 長度或其它定義的 weight，比如說經 過這條 edge 所要花費的 costn如果是 unweighted edge，一般來說 edge 的長度就是等於 1nvertex 的 weightn用來表示這個 vertex 的重要性或其它定義的 weight，比如 說經過這個 vertex 所要花費的 costn如果是 unweighted vert
3、ex，一般來說 vertex 的 weight 就是 等於 15基本定義ndegreen定義在 vertex 上nundirected graphnvertex 的 degree 就等於跟這個 vertex 相連的 edge 個數ndirected graphnvertex 的 degree 分成兩種nindegreen所有指向這個 vertex 的 edge 個數noutdegreen所有由這個 vertex 指出去的 edge 個數6undirecteddirecteddegree = 3indegree = 2 outdegree = 2Example7建議n當看到一個題目時，如果是 g
4、raph 上的題目或 是要轉成 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-edge: Ai,
5、 j 存由 vertex i 到 vertex j 這條 edge 的 weight ( 表示這條 edge 不存在)nAdjacency-listn開 n 個 list，總共的 size 是 n + mnm 為 edge 的個數n每個 list 後面接著跟這個 vertex 可連到的 vertex9Example: undirected014320 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-matrix0 1 2 3 41 0 1 1 34 4 3 4 0/22 1/ /3/ad
6、jacency-list10 -1 表示 nil 有 edge length 時使用另一個陣列 len2mAdjacency-list 存法014320 1 3 3 41 0 1 1 34 4 3 4 0/22 1/ /3/i01234567891 01 11 21 3 adjn09681 1 node2m14442313102301next2m1-11 045-17-123-11 21 3-181 24 102 -111014320 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-ma
7、trix0 1 2 3 41 2 3 1 3/ / /4 4/ /adjacency-listExample: directed12Graph 存法n建議用 adjacency-matrixn方便，好寫n可直接查表知道 vertex i 和 vertex j 之間相連 的情況 (用 adjacency-list 的話需要 scan list 一次)n雖然較花 memory 和時間，不過絕大部分的 題目用 adjacency-matrix 就夠了13常見的 input 給法 (I)n給一堆 edge 1 3 2 5 1 5 5 4 2 3 4 2 3 4n每次讀進一條 edge 之後，就把它加入
8、 adjacency-matrix 之中，記 得要看清楚題目的 edge 有沒有方向性，如果是 undirected 的 edge ，要記得雙向 edge 都要加n比如讀到 1 3 這條 edge，而且是 undirected，就表示 1 到 3 和 3 到 1 都有 edge14常見的 input 給法 (II)n直接給 adjacency-list 或 adjacency-matrix 2 50 1 0 0 1 1 5 3 41 0 1 1 1 2 4或0 1 0 1 0 2 5 30 1 1 0 1 4 1 21 1 0 1 0n直接讀進來存進 adjacency-matrix 中就好1
9、5常見的 input 給法 (III)n給法跟前面兩種很像，只是 vertex 的編號可能 很大，而不是 1 到 n，或是 vertex 的編號不是 數字 1 100000abc def 100000 33333或def eas 33333 1eas abcn不可能有機會讀到多大的數字就開多大的二維 陣列n也沒辦法用英文字做陣列的 index16解決方法n需要做 re-label 的動作n把 1 = 0, 33333 = 1, 100000 = 2, n把 abc = 0, def = 1, eas = 2, n因為只出現三種數字，所以只要開一個 3 3的二維陣列，再加上一個用來做 mappi
10、ng 的表就好17133333 100000012原來的數字re-label 後的數字011101110Exampleadjacency-matrix18解決方法n要是 vertex 的個數不少，每次如果要去查 mapping 的 表時，如果都做 linear search 時間可能會花蠻多n在做 re-label 的時候，可以先 sort 好之後再做 mapping 的動作，這樣之後要去查表的時侯就可以用 binary search 來查，可以省一些時間n先讀進所有 input 存起來nsort 後造表n最後再建 adjacency-matrix19DFS and applicationsn
11、Depth-first search (DFS)nConnected componentnStrongly connected componentnTopological sort20Depth-first search (DFS)n如同名字一樣，是一種以深度 (depth) 為 優先 (first) 所做的 traversal (search)n在暴力法，tree traversal 上都有相類似的 概念21DFS on graphn任挑一個 vertex v 當起點，從 adjv 中挑一個沒走過的 vertex 往下走，因為要以深度為優先，所以走到下一個 vertex 之後，就再看看能不能
12、繼續往下走到一個沒走過 的 vertex ，如果可以的話就往下走，不行的話就回頭 看看之前還有沒有別條路可以走n當走到都沒有路可走的時侯，就看看是不是還有沒被 走到的 vertex，有的話就再挑一個點起點，繼續做 traversal 的動作n走過的 vertex 不要重覆走n要記錄 vertex 有沒有被走過22Example23Data structure for DFSnvisit 陣列n記錄 vertex 是否被走過nstart 陣列n記錄 vertex 在第幾步的時侯第一次被看到nfinish 陣列n記錄 vertex 在第幾步的時侯發現無路可走，要回到 前一個 vertex 上24E
13、xample1/2/3/4/9/10/4/53/62/71/810/119/1225Pseudo codeDFS (G) for each vertex v VG visitv = 0; time = 0; for each vertex v VG if (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 adj
14、acency-matrix for (i = 0; i n; i+) if (adjvi = 1)27Summary: DFSnDFS 只是一種概念，該怎麼用其實主要 看題目而定nstart 和 finish time 也不一定會用到，如果 題目沒有需要的話也可以省略28Connected componentn對 undirected graph 來說，給一堆 vertices ，如果這裡面任兩個 vertices 都可以走到 對方的話，那這一堆 vertices 就屬於同一 個 connected componentn如果是 directed graph，則稱作 strongly conne
15、cted component29例題講解: A. 459 http:/acm.uva.es/p/v4/459.htmln給一個 undirected graph，vertex 是由 A 到 Z 來編號ninput 給法是給所有的 edgen試問: 這個 undirected graph 中共有幾個 connected component30Sample input/outputSample input 1E AB CE DB ECSample output 2vertex 編號最大會到 E31SampleADB CE共兩個 connected component32解法n找一個還沒被找過的點，由它開始做 DFS，所有能到達的點都是屬於同一個 connected componentn當沒有路可以走的時侯，就找看看還有 沒有沒被走過的點，有的話就從它開始 做 DFS，這些點則屬於另一個 connected component33n因為是 undirected graph，edge 沒有方向 性，所以讀進一條 edge 時要記得兩個方 向的 edge 都要存n這個題目不需要 start 和 finish time34Strongly connected componentn對 directed graph 來說，給一堆 vertices， 如果這裡面任兩個 verti
