主题graph表示法和dfs

《主题graph表示法和dfs》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主題:Graph:表示法與DFS解題技巧基本定義Graph表示法(存法)DFSandapplications例題講解歷年題目1基本定義Graph由vertices和edges所組成2基本定義undirectedV.Sdirected定義在edge上undirectededgeedge沒有方向性，如果說a和b之間有一條edge，則表示a可經由這條edge到b，b也可由這條edge到adirectededgeedge有方向性，比如說a到b有一條edge，則表示a可經由這條edge到b，但是b不能由這條e

2、dge到a3undirecteddirectedExample4基本定義unweightedV.Sweighted可定義在vertex上或是edge上edge的weight用來表示這個edge長度或其它定義的weight，比如說經過這條edge所要花費的cost如果是unweightededge，一般來說edge的長度就是等於1vertex的weight用來表示這個vertex的重要性或其它定義的weight，比如說經過這個vertex所要花費的cost如果是unweightedvertex，一般來

3、說vertex的weight就是等於15基本定義degree定義在vertex上undirectedgraphvertex的degree就等於跟這個vertex相連的edge個數directedgraphvertex的degree分成兩種indegree所有指向這個vertex的edge個數outdegree所有由這個vertex指出去的edge個數6undirecteddirecteddegree=3indegree=2outdegree=2Example7建議當看到一個題目時，如果是graph上

4、的題目或是要轉成graph來做的題目的話，首先要判斷這個graph是directed或undirected，是weighted或unweighted，是不是一些比較特殊的graph，因為所要存的資料，適用的演算法，解題技巧都不太一樣8Graph表示法(存法)Adjacency-matrix開一個二維陣列，size是n×nn為vertices的個數unweighted-edge:A[i,j]=1代表由vertexi到vertexj有一條edge，A[i,j]=0代表沒有weighted-edge:A[

5、i,j]存由vertexi到vertexj這條edge的weight(表示這條edge不存在)Adjacency-list開n個list，總共的size是n+mm為edge的個數每個list後面接著跟這個vertex可連到的vertex9Example:undirected0143201234001001110111201010301101411010adjacency-matrix012341011344340//221//3/adjacency-list10-1表示nil有edgelength

6、時使用另一個陣列len[2m]Adjacency-list存法01432013341011344340//221//3/i012345678910111213adj[n]096811node[2m]14442313102301next[2m]1-11045-17-123-11213-18124102-1110143201234001001100101200010301000400010adjacency-matrix0123412313///44//adjacency-listExample:dir

7、ected12Graph存法建議用adjacency-matrix方便，好寫可直接查表知道vertexi和vertexj之間相連的情況(用adjacency-list的話需要scanlist一次)雖然較花memory和時間，不過絕大部分的題目用adjacency-matrix就夠了13常見的input給法(I)給一堆edge13251554234234每次讀進一條edge之後，就把它加入adjacency-matrix之中，記得要看清楚題目的edge有沒有方向性，如果是undirected的edge

8、，要記得雙向edge都要加比如讀到13這條edge，而且是undirected，就表示1到3和3到1都有edge14常見的input給法(II)直接給adjacency-list或adjacency-matrix250100115341011124或010102530110141211010直接讀進來存進adjacency-matrix中就好15常見的input給法(III)給法跟前面兩種很像，只是vertex的編號可能很大，而不是1到n，或是vertex的編號不是數