主题Graph表示法与DFS.ppt
《主题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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 主题 Graph 表示 DFS
链接地址:https://www.31doc.com/p-2714435.html