最新主题Graph表示法与DFS课件

,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,主题Graph表示法与DFS,主题Graph表示法与DFS,基本定義,Graph,由,vertices,和,edges,所組成,2,基本定義Graph2,最新主题Graph表示法与DFS课件,最新主题Graph表示法与DFS课件,最新主题Graph表示法与DFS课件,最新主题Graph表示法与DFS课件,最新主题Graph表示法与DFS课件,最新主题Graph表示法与DFS课件,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 j 這條 edge 的 weight(,表示這條 edge 不存在),Adjacency-list,開 n 個 list，總共的 size 是 n+m,m 為 edge 的個數,每個 list 後面接著跟這個 vertex 可連到的 vertex,9,Graph 表示法(存法)Adjacency-matrix,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,/,adjacency-list,10,Example:undirected01432 0,-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,/,i,0,1,2,3,4,5,6,7,8,9,10,11,12,13,adjn,0,9,6,8,11,node2m,1,4,4,4,2,3,1,3,1,0,2,3,0,1,next2m,1,-1,10,4,5,-1,7,-1,2,3,-1,12,13,-1,8,1,2,4,10,2,-1,11,-1 表示 nilAdjacency-list 存法014,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:directed,12,01432 0 1 2 3 4 adjace,Graph 存法,建議用 adjacency-matrix,方便，好寫,可直接查表知道 vertex i 和 vertex j 之間相連的情況(用 adjacency-list 的話需要 scan list 一次),雖然較花 memory 和時間，不過絕大部分的題目用 adjacency-matrix 就夠了,13,Graph 存法建議用 adjacency-matrix13,常見的 input 給法(I),給一堆 edge,1 3,2 5,1 5,5 4,2 3,4 2,3 4,每次讀進一條 edge 之後，就把它加入 adjacency-matrix 之中，記得要看清楚題目的 edge 有沒有方向性，如果是 undirected 的 edge，要記得雙向 edge 都要加,比如讀到 1 3 這條 edge，而且是 undirected，就表示 1 到 3 和 3 到 1 都有 edge,14,常見的 input 給法(I)給一堆 edge14,常見的 input 給法(II),直接給 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 0,直接讀進來存進 adjacency-matrix 中就好,15,常見的 input 給法(II)直接給 adjacency,常見的 input 給法(III),給法跟前面兩種很像，只是 vertex 的編號可能很大，而不是 1 到 n，或是 vertex 的編號不是數字,1 100000abc def,100000 33333或def eas,33333 1eas abc,不可能有機會讀到多大的數字就開多大的二維陣列,也沒辦法用英文字做陣列的 index,16,常見的 input 給法(III)給法跟前面兩種很像，只是,解決方法,需要做 re-label 的動作,把 1=0,33333=1,100000=2,把 abc=0,def=1,eas=2,因為只出現三種數字，所以只要開一個 3 3的二維陣列，再加上一個用來做 mapping 的表就好,17,解決方法需要做 re-label 的動作17,1,33333,100000,0,1,2,原來的數字,re-label 後的數字,0,1,1,1,0,1,1,1,0,Example,adjacency-matrix,18,133333100000012原來的數字re-label 後,解決方法,要是 vertex 的個數不少，每次如果要去查 mapping 的表時，如果都做 linear search 時間可能會花蠻多,在做 re-label 的時候，可以先 sort 好之後再做 mapping 的動作，這樣之後要去查表的時侯就可以用 binary search 來查，可以省一些時間,先讀進所有 input 存起來,sort 後造表,最後再建 adjacency-matrix,19,解決方法要是 vertex 的個數不少，每次如果要去查 ma,DFS and applications,Depth-first search(DFS),Connected component,Strongly connected component,Topological sort,20,DFS and applicationsDepth-firs,Depth-first search(DFS),如同名字一樣，是一種以深度(depth)為優先(first)所做的 traversal(search),在暴力法，tree traversal 上都有相類似的概念,21,Depth-first search(DFS)如同名字一樣,DFS on graph,任挑一個 vertex v 當起點，從 adjv 中挑一個沒走過的 vertex 往下走，因為要以深度為優先，所以走到下一個 vertex 之後，就再看看能不能繼續往下走到一個沒走過的 vertex，如果可以的話就往下走，不行的話就回頭看看之前還有沒有別條路可以走,當走到都沒有路可走的時侯，就看看是不是還有沒被走到的 vertex，有的話就再挑一個點起點，繼續做 traversal 的動作,走過的 vertex 不要重覆走,要記錄 vertex 有沒有被走過,22,DFS on graph任挑一個 vertex v 當起點，,Example,23,Example23,Data structure for DFS,visit 陣列,記錄 vertex 是否被走過,start 陣列,記錄 vertex 在第幾步的時侯第一次被看到,finish 陣列,記錄 vertex 在第幾步的時侯發現無路可走，要回到前一個 vertex 上,24,Data structure for DFSvisit 陣列,Example,1/,2/,3/,4/,9/,10/,4/5,3/6,2/7,1/8,10/11,9/12,25,Example1/2/3/4/9/10/4/53/62/71,Pseudo code,DFS(G),for each vertex v,VG,visitv=0;,time=0;,for each vertex v VG,if(visitv=0),DFS_visit(v);,26,Pseudo codeDFS(G)26,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-matrix,for(i=0;i n;i+),if(adjvi=1),27,Pseudo codeDFS_visit(v)scan,Summary:DFS,DFS 只是一種概念，該怎麼用其實主要看題目而定,start 和 finish time 也不一定會用到，如果題目沒有需要的話也可以省略,28,Summary:DFSDFS 只是一種概念，該怎麼用其實主,Connected component,對,undirected graph,來說，給一堆 vertices，如果這裡面任兩個 vertices 都可以走到對方的話，那這一堆 vertices 就屬於同一個 connected component,如果是,directed graph,，則稱作,strongly connected component,29,Connected component對 undirecte,例題講解:A.459,http:/acm.uva.es/p/v4/459.html,給一個 undirected graph，vertex 是由 A 到 Z 來編號,input 給法是給所有的 edge,試問:這個 undirected graph 中共有幾個 connected component,30,例題講解:A.459http:/acm.uva.es,Sample input/output,Sample input,1,E,AB,CE,DB,EC,Sample output,2,vertex 編號最大會到 E,31,Sample input/outputSample inpu,Sample,A,D,B,C,E,共兩個 connected component,32,SampleADBCE共兩個 connected compo,解法,找一個還沒被找過的點，由它開始做 DFS，所有能到達的點都是屬於同一個 connected component,當沒有路可以走的時侯，就找看看還有沒有沒被走過的點，有的話就從它開始做 DFS，這些點則屬於另一個 connected component,33,解法找一個還沒被找過的點，由它開始做 DFS，所有能到達的點,因為是 undirected graph，edge 沒有方向性，所以讀進一條 edge 時要記得兩個方向的 edge 都要存,這個題目不需要 start 和 finish time,34,因為是 undirected graph，edge 沒有方向,Strongly connected component,對 directed graph 來說，給一堆 vertices，如果這裡面任兩個 vertices 都有 directed path的話，就屬於同一個 strongly connected component,35,Strongly connected component對,Example,a,b,c,d,e,f,g,h,共有