主题Graph表示法与DFS.pptVIP

主題: Graph:表示法與 DFS 解題技巧 基本定義 Graph 表示法 (存法) DFS and applications 例題講解 歷年題目 基本定義 Graph 由 vertices 和 edges 所組成 基本定義 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 到 b，但是 b 不能由這條 edge 到 a Example 基本定義 unweighted V.S weighted 可定義在 vertex 上或是 edge 上 edge 的 weight 用來表示這個 edge 長度或其它定義的 weight，比如說經過這條 edge 所要花費的 cost 如果是 unweighted edge，一般來說 edge 的長度就是等於 1 vertex 的 weight 用來表示這個 vertex 的重要性或其它定義的 weight，比如說經過這個 vertex 所要花費的 cost 如果是 unweighted vertex，一般來說 vertex 的 weight 就是等於 1 基本定義 degree 定義在 vertex 上 undirected graph vertex 的 degree 就等於跟這個 vertex 相連的 edge 個數 directed graph vertex 的 degree 分成兩種 indegree 所有指向這個 vertex 的 edge 個數 outdegree 所有由這個 vertex 指出去的 edge 個數 Example 建議 當看到一個題目時，如果是 graph 上的題目或是要轉成 graph 來做的題目的話，首先要判斷這個 graph 是 directed 或 undirected，是 weighted 或 unweighted，是不是一些比較特殊的 graph，因為所要存的資料，適用的演算法，解題技巧都不太一樣 Graph 表示法 (存法) Adjacency-matrix 開一個二維陣列，size 是 n × n n 為 vertices 的個數 unweighted-edge: A[i, j] = 1 代表由 vertex i 到 vertex j 有一條 edge，A[i, j] = 0 代表沒有 weighted-edge: A[i, j] 存由 vertex i 到 vertex j 這條 edge 的 weight (? 表示這條 edge 不存在) Adjacency-list 開 n 個 list，總共的 size 是 n + m m 為 edge 的個數 每個 list 後面接著跟這個 vertex 可連到的 vertex Example: undirected Adjacency-list 存法 Example: directed Graph 存法 建議用 adjacency-matrix 方便，好寫 可直接查表知道 vertex i 和 vertex j 之間相連的情況 (用 adjacency-list 的話需要 scan list 一次) 雖然較花 memory 和時間，不過絕大部分的題目用 adjacency-matrix 就夠了 常見的 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 常見的 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 中就好 常見的 input 給法 (III) 給法跟前面兩種很像，只是 vertex 的編號可能很大，而不是 1 到 n，或是 ver