資料結構與演算法 第6章 圖形 徐熊健.

Presentation on theme: "資料結構與演算法 第6章 圖形 徐熊健."— Presentation transcript:

1 資料結構與演算法 第6章 圖形 徐熊健

2 目錄 6.1 問題的圖形表示法 6.2 圖形的資料表示 6.3 圖形的走訪或搜尋 6.4 延展樹和最小成本延展樹 6.5 最短路徑
6.6 遞移封閉 6.7 拓樸序列

3 6.1 問題的圖形表示法 圖形是包含點、和連接點的邊，所構成的離散結構
有時在邊上可能加上權重值 (weight) 或成本值 (cost) 。

4 6.1.1尤拉迴路 (Euler Circuit) 西元1763年，尤拉 (Leonhard Euler) 即利用圖形來描繪Konigsberg 的七橋問題 (Konigsberg bridge problem)。 圖6-1 Kouigsberg當時之地理簡圖 圖6-2 圖形表示

5 6.1.2 漢米爾頓迴圈 (Hamiltonian Cycle)
在1800年代早期，William Rowan Hamilton提出了一個有趣的問題：在如圖6-3 (a) 的十二面體中，每一頂點代表一個城市，那麼是否能找個一條迴路 (cycle) ，走過每一城市恰巧一次，且回到原出廢城市（此終點即為起點，遂它可走過2次）。 圖6-3 漢米爾頓迴圈的由來

6 6.1.3旅行銷售員問題 (Traveling Salesperson Problem)
旅行銷售員為推銷公司的商品，希望自公司出發走訪所有指定的城市，且不重複，並回到公司；而走過路徑的總距離（或總花費）要最短（或最小）。這個問題有城市間實際距離（或旅行花費）的考量。 圖6-5 城市交通圖形表示

7 6.1.4頂點覆蓋(Vertex Cover)問題 將博物館的展示空間用圖形來表示，擺放藝術品的直線走道是邊，頂點是邊與邊交界處。
基於安全的考量，館方將設置最少的警衛希望能監看所有的展示走道。 這就是典型的頂點覆蓋問題：在圖形中，挑最小的頂點集合，使得任何一邊的兩個頂點中，至少有一頂點在所挑的集合中，（所挑的點集合可覆蓋所有的點）。 所挑出的頂點，其分支出的邊，即稱其能覆蓋 (cover) 的邊。

8 6.2 圖形的專有名詞 我們常用G = (V, E) 來描述一個圖形，其中 V是一個包含所有頂點有限集合 E是連接V中頂點的邊所構成的集合
6.2 圖形的專有名詞 我們常用G = (V, E) 來描述一個圖形，其中 V是一個包含所有頂點有限集合 E是連接V中頂點的邊所構成的集合 V = {v1, v2,…, vn} E = {e1, e2,…, em} n > 0，m  0。

9 6.2 圖形的專有名詞 無向圖、有向圖 若邊不具方向性，稱為「無向圖」(undirected graph) 完整圖
6.2 圖形的專有名詞 無向圖、有向圖 若邊不具方向性，稱為「無向圖」(undirected graph) G1和G3為無向圖，G2為有向圖 完整圖 在n個頂點的無向圖中，最多可能有n(n-1)/2條邊。若n個頂點的無向圖的確有偌多邊，則稱此圖形為「完備圖」 (complete graph)。

10 6.2 圖形的專有名詞 圖6-9 完備圖

11 6.2 圖形的專有名詞 相鄰、連接、分支度 G = (V, E) 為一圖形，如果 (u, v)  E，則稱u和v兩頂點「相鄰」 (adjacent) ，且 (u, v) 「連接」 (incident on) 頂點u和v。 若G的邊有方向性，且 <u, v>  E，則稱u「相鄰至」 (adjacent to) v；且v從u相鄰 (adjacent from) ；或 <u, v> 連接頂點u和v。 所有連接在無向圖頂點u上的總邊數，稱為u的「分支度」 (degree) 。 所有以有向圖頂點u為頭的邊數，為u的「向外分支度」 (out-degree) ； 所有以有向圖頂點u為尾的邊數，為u的「向內分支度」 (in-degree) 。

12 6.2 圖形的專有名詞 子圖 　圖形G = (V, E) 的「子圖」 (subgraph) G‘ = (V’, E‘) ，必須滿足V’  V且E‘  E。 圖 (b)、(c)、(d) 是圖 (a) 的子圖。 圖 (f)、(g)、(h) 是圖 (e) 的子圖。

13 6.2 圖形的專有名詞 路徑，簡單路徑、長度、迴圈
6.2 圖形的專有名詞 路徑，簡單路徑、長度、迴圈 在圖形中，一條從u到v的「路徑」 (path) ，是由頂點u---…--v及其連接的邊 (u,), (,), …, (, v) （或 <u,>, <,>, …, <,v>）所構成；我們以u---…--v表示此u到v的路徑。 一條路徑的「長度」 (length) 即為該路徑包含的所有邊數。 一條「簡單路徑」 (simple path) 指的是除了起點和終點外，其它的頂點皆不同的路徑。 「迴圈」 (cycle) 指的是起點和終點相同的簡單路徑。

14 6.2 圖形的專有名詞 相連的頂點、或圖形、相連組合
6.2 圖形的專有名詞 相連的頂點、或圖形、相連組合 在無向圖形G = (V, E) 中，如果頂點u存在一條路徑連接到頂點v，則稱頂點u和v是「相連的」 (connected) ，（也可說是v和u是相連的）； 而「無向圖形是相連的」表示任兩個頂點u和v皆為相連的。 無向圖形G的「相連組合」 (connected component) C指的是圖中的最大相連的子圖，應即C是G的相連子圖中最大的。

15 6.2 圖形的專有名詞 強固相連、強固相連組合 在有向圖形G = (V, E) 中，若G的任兩個頂點u和v，都有兩條路徑，一條由u往v，一條由v往u，則稱G為「強固相連的」 (strongly connected) 。 「強固相連組合」 (strongly connected component) 指的是有向圖形中，最大而且強固相連的子圖。

16 6.2 圖形的專有名詞 圖中G8不是強固相連的，因至少存少3往2無路徑可通。而 G8的強固相連組合為C2。

17 6.2 圖形的專有名詞 沒有迴圈 不存在迴圈的圖形稱為「沒有迴圈」 (acyclic) ，一棵樹即為相連、但沒有迴圈的圖形。
6.2 圖形的專有名詞 沒有迴圈 不存在迴圈的圖形稱為「沒有迴圈」 (acyclic) ，一棵樹即為相連、但沒有迴圈的圖形。 圖形是比樹更一般化的資料結構，自然原先對樹所做的動作或運算均可在圖形上探索。

18 6.2 圖形的資料表示 就像樹一樣，圖形也可用不同的資料結構來表示，下面我們介紹二種常用的資料結構：「相鄰矩陣」和「相鄰串列」。
6.2 圖形的資料表示 就像樹一樣，圖形也可用不同的資料結構來表示，下面我們介紹二種常用的資料結構：「相鄰矩陣」和「相鄰串列」。 那種資料結構比較適合，則視圖形的種類、應用的範疇及需要的運算而定。

19 6.2.1 相鄰矩陣 相鄰矩陣 (adjacent matrix) 即將圖形中頂點是否相鄰的關係紀錄在矩陣中。
相鄰矩陣 相鄰矩陣 (adjacent matrix) 即將圖形中頂點是否相鄰的關係紀錄在矩陣中。 若G = (V, E) ，而 |V| = n，即G有n個頂點，則任兩點是否相鄰可用一個存放0和1的nn二維陣列A表示之： 令i, j  V 若 (i, j)  E （或<i, j>  E），則令A[i][j]=1 否則令A[i][j]=0。

20 相鄰串列 若圖形中頂點u的分支度為k，我們可以將與u相鄰的這k個頂點用鍵節串列存放之，那麼如此形成的n個鍵結串列，即構成此圖形的相鄰串列 (adjacent list) 表示。

21 6.3圖形的走訪或搜尋 如對樹的走訪一樣 ，我們也希望對存放在圖形中節點的資料，決定其處理的順序，所以有走訪或搜索圖形資料的基本運算。
有兩種常用的圖形走訪或搜尋演算法： (1)深先搜尋 (depth-first search) (2)廣先搜尋 (breathe-first search)

22 6.3.1深先搜索 深先搜索強調不斷地往圖形的深處走訪。從某一頂點u出發。
選擇一個與u相鄰且尚未走訪的頂點v走去，再以v為起點，選擇其尚未走訪的相鄰頂點走去； 若頂點w的所有相鄰頂點皆已走訪過，則回到當時從s走去w的頂點s，自s往下走訪； 當所有頂點都被走訪過時，走訪即可停止。

23 6.3.1深先搜索 演算法6-1：遞迴深先搜尋 輸入：圖形G = (V, E)， V = {0, 1, 2, ..., n-1}
1 int visited[n], i; 2 void DFS(int u) 3 { visited[n] = 1; 4 印出u; 5 for (所有與u相鄰的頂點v) 6 if (v未曾走訪，即visited[v]≠1) 7 { 印出v；DFS(v) } ; 8 } 9 main() 10 { for (i=0; i＜n ; i++) visited[i] = 0; 11 DFS(0); 12 }

24 6.3.1深先搜索 遞迴的使用雖然方便，但執行效率稍為遜色，我們可利用堆疊改寫如下： 演算法6-2：堆疊深先搜尋
輸入：圖形G = (V, E), V = {0, 1, 2, ..., n-1} 輸出：G的深先搜尋頂點順序 1 int visited[n], i; 2 void DFS(int u) 3 { push(u); 4 while (堆疊內仍有頂點資料) 5 { pop(v); 6 印出v; 7 visited[v] = 1; 8 if (w為v尚未走訪的相鄰頂點, 即 visted[w] ≠ 1) 9 push(w); 10 } 11 } 12 main() 13 { for (i=0; i＜n; i++) visited[i] = 0; 14 DFS(0); 15 }

25 6.3.2廣先搜尋 廣先搜尋 (breadth-first search) 強調先走訪一頂點 u的所有相鄰頂點！
從一頂點出發，先逐一走訪 u的所有相鄰頂點v1, v2,…., vk； 再自 v1走訪其所有的相鄰頂點、爾後再自 v2走訪其所有的相鄰頂點、再v3、…、vk。 如此一層一層地廣先搜尋，直至走訪完所有的頂點為止。 由於先走訪的點，會先對其相鄰頂點進行廣先搜尋：後走訪者，則後考慮。 可以用佇列來存放以走訪的頂點。

26 6.3.2廣先搜尋 演算法6-3：廣先搜尋 輸入：圖形G = (V, E), V = {0, 1, 2, ..., n-1}
1 int visited[n], i; 2 main() 3 { int v; 4 for (i=0; i<n; i++) visited[i] = 0; 5 visited[0] = 1; 6 Add_Queue(0); 7 while (Queue仍有頂點資料) 8 { v = Delete_Queue(); 9 印出v; 10 for (所有與v相鄰的頂點w) 11 { if (visited(w) == 0) 12 { visited(w) = 1; Add_Queue[w]; 14 } 15 } 16 } 17 }

27 6.3.3 尋找圖形的連通組合 欲找出無向圖形G中的連通組合，只要對G中尚未走訪過的點u做深先搜尋或廣先搜尋，即可將包含u的連通子圖Cu找出來， 若 v不在 Cu中則再對 v做深先或廣先搜尋，則可得包含 v的連通子圖Cv； 這個步驟對所有尚未走訪的點都做，即可得出所有的連通子圖； 其中最大的連通子圖極為連通組合。

28 6.3.3 尋找圖形的連通組合 演算法 6-4： 輸入：圖形G = (V, E)， V = {0, 1, 2, ..., n-1}
1 for (i=0; i＜n; i++) do visited[i] = 0; 2 for (i=0; i＜n; i++) do 3 { if (visited[i] == 0) 4 { cout << “新的連通子圖”<<endl; 5 DFS(i); 6 } 7 }

29 6.4 延展樹和最小成本延展樹 6.4.1 延展樹 若圖形G = (V, E) 本身是相連的，則從任一頂點開始利用深先或廣先搜尋，即可走訪G中的所有頂點V。 若將搜尋過程中曾走訪的邊，組織成集合ET，未曾走訪的邊組織成集合EN，則 E=ET ∪EN 且 ET∩EN =； 頂點的集合V和曾走訪的邊集合ET，會構成一棵樹T = (V, ET)，我們稱T為G的延展樹 (spanning tree)—亦即T以樹的結構，延展出G中的所有頂點。

30 6.4.2最小成本延展樹 在圖形G = (V, E) 的所有邊上，加上權重值 (weight) ，即w(e) ，e  E，那麼G中的延展樹，皆有其權重值的總和，我們稱之為成本 (cost) ； 「最小成本延展樹」 (minimum–cost spanning) ，即為加權圖形中，所有延展樹裏面成本最小者。 由於在實際應用上的重要價值，最小成本延展樹引起了許多學者的興趣與討論；其中有三個著名的演算法先後被提出來—這三種方法都採用了「貪婪策略」 (greedy strategy) —分別是 (1) Kruskal演算法 (2) Prim演算法 (3) Sollin演算法

31 Kruskal演算法 Kruskal認為每次加入一條最小成本的邊，應對最後想要的最小成本延展樹有所貢獻；亦即Kruskal的貪婪策略，就是逐次加入最小成本的邊，而一旦形成迴圈，將不符合樹的條件，遂直接捨去之； 若原圖形有n個頂點，則在共加入n-1條邊後停止。此時此n-1條邊，連出n個頂點，沒有迴路，正是一棵延展樹。 這個演算法已被證明—確實可找出最小延展樹。

32 6.4.2.1 Kruskal演算法 演算法 6-5 Kruskal演算法求最小延展樹
輸入：加權圖形G = (V, E)，|V| = n; w(e)為邊e上的成本 輸出：T，T為G的最小延展樹 1 T = ; 2 while ((T中少於n-1條邊) && (E != )) 3 { (u, v) = E中最小成本的邊; 4 E = E∖{(u, v);} 5 if ((u, v)加入T後不致形成迴圈) 6 T = T∪{(u, v);} 7 } 8 if (T中邊數<(n-1)) 印出”G無延展樹！”; 9 else輸出T;

33 Prim演算法 在尋找最小成本延展樹的過程中，Prim認為可以任意挑一頂點開始，選出與其連接的邊中最小者，將此邊連接的頂點加入，稱之為目前的最小延展樹T； 反覆「挑與T連接的最小邊」，將邊連接的頂點加入T，俟T包含n-1條邊為止。亦即Prim的貪婪策略是—每次挑與T連接具最小成本的邊。

34 6.4.2.2 Prim演算法 演算法6-6 Prim演算法求最小延展樹 輸入：加權圖形G = （V, E）, ｜V｜ = n;
輸出：T，T為G的最小延展樹。 1 T = ; 2 While (T中少於n-1條邊) 3 { (u, v) = min{(a, b)∣aT且bV-T} 4 if((u, v)不存在) break; 5 T = T∪{(u, v)}; 6 } 7 if (T中邊數<(n-1)) 印出”G無延展樹！”; 8 else 輸出T;

35 Prim演算法 試比較一下，Kruskal演算法每次加入「所有尚未考慮的邊中具最小成本者」，所以在執行過程中，Kruskal演算法產生的是一群樹的集合，即森林；而Prim演算法的執行過程，一定產生「目前最小成本的延展樹」，它是一棵樹。 Kruskal演算法得考慮：邊的加入是否形成迴圈；Prim 演算法則不必。 Kruskal演算法一定得從所有邊中成本最小者開始建樹；Prim演算法則可任意挑建樹的起點。 縱使兩個演算法有以上的差異，兩者產生的最小成本延展樹的「成本」是一樣的。

36 Sollin演算法 以Sollin演算法建立最小成本延展樹，可視為Prim演算法的平行處理 (parallel processing) 的版本。我們可視圖形上的所有頂點各自是棵樹，那麼Sollin的想法是讓每棵樹引用Prim的概念—每棵樹皆加入最小成本的邊—去擴張； 當兩棵樹擴張時用了共同的邊、或共同的頂點，則此二棵樹彼此相連，可合併成一棵樹； 當所有小樹皆合併成唯一的一棵大樹即停止，最小成本延展樹亦即求得。

37 6.5 最短路徑 加權圖形的結構，非常適合用來描述城市間的交通狀況：用頂點代表城市，邊代表城市間連接的道路，邊上的權重值為該道路的距離（或往來的成本，在此我們以距離討論之）。 那麼從城市甲到城市乙的最短路徑 (shortest path)，當然是重要的實際考量，本節即討論這個主題，我們將告訴各位自城市甲，經過哪些道路和城市可有最短的距離到達城市乙。依據起點的不同，本節最短路徑的問題有兩種型式： (1) 單一起點當其他所有目的地 (single source/all destination) (2) 所有任意兩點間 (all pairs) 的最短路徑

38 6.5.1 單一起點到所有目的地之最短路程 首先在加權圖形G = (V, E) 中，令所有的邊上的距離w(ei)  0，ei  E，1 ≤ i ≤ |E|； 想知道自起點u  V，到其他所有城市v  V-{u} 的最短路徑，我們稱之為「單一起點到所有目的地」之最短路徑問題。

39 6.5.1 單一起點到所有目的地之最短路程 演算法 6-7 Dijkstra演算法求單一起點到所有目的地的最短路程
輸入：加權圖形G(V, E)，V={0, 1, 2, ..., n-1}，邊上的距離為w[i，j]，i, jV，起點u 輸出：u到v的最短距離，vV，u≠v 1 for (j=0; j<n; j++) D[j] = w[u, j]; 2 found[u] = true; D[u] = 0; 3 while (尚未求出到所有目的地的最短距離) 4 { v = D中最小且 found[v] = false; 5 found[v] = true; 6 for (k=0; (k<n) && (found[k] == false); k++) 7 D[w]= min(D[w], D[k]+w[k, v]); 8 }

40 6.5.2任意兩點間的最短路徑 在本節中我們介紹「任意兩點間最短路徑」（all pairs shortest paths）的解法。當然這個問題可以用Dijkstra演算法，把每點頂點都當成起點各執行一次，共O(n) 次（每次時間為O(n2)），總共以O(n3) 的時間，得到任意兩點間的最短路徑。 然而本節將採用「動態規劃」 (dynamic programming) 的策略，來設計求解此問題的演算法，雖然時間複雜度亦為O(n3) ，但在概念上是不一樣的思考方向。 我們用相鄰距離矩陣W來表示圖形G = (V, E )，V = {0, 1, 2,…,n-1}，w[i][j]為i到j的相鄰距離0 ≤ i, j ≤ n-1。 由於自i到j可能經過其他許多頂點，也許是頂點0, 1, 2, …, n-1；我們可以用Ak[i][j]來表示「i到j途中允許經過頂點代碼不大於k的最短路徑」。 此矩陣的起始狀況為： A-1[i][j] = w[i][j] 而且一旦求出An-1[i][j]，即可知道「自i到j途中允許經過0, 1, 2, …, n-1頂點的最短路徑」，這也本是我們想求得的解答。於是我們的任務即希望求出：A0, A1, A2,…, An-1。

41 6.5.2任意兩點間的最短路徑 如果Ak-1已經求出，該如何利用之求出Ak呢，1 ≤ k ≤ n-1？下面有兩種可能：
(1)若自i往j不經過頂點k，那麼Ak-1[i][j]已存放了這個最短路徑 (2)若自i往j會經過頂點k，則經過路徑可區分為兩段：分別是自i往k，和由k往j兩段。由於到目前為止，自i往k和由k往j這兩段路徑，皆不至於經過頂點代碼超過k的頂點，所以這兩段路徑的最短距離應分別為Ak-1[i][k]和Ak-1[k][j]。 由上面兩種可能，我們可推出：Ak欲保存自i到j，途中不經過頂點代碼大於k的最短距離，Ak必須以下式求出： Ak[i][j] = min{Ak-1[i][j], Ak-1[i][k]+Ak-1[k][j]}, 0 ≤ k ≤ n-1。 注意這裡的Ak所引用的值皆在Ak-1中，Ak-1亦必定先於Ak被求出；所以我們可以同一個陣列來存放Ak。

42 6.5.2任意兩點間的最短路徑 演算法6-8：任意兩頂點間的最短距離
輸入：圖形G = (V， E )，V ={0, 1, 2, ..., n-1}和其相鄰矩陣w[i][j]， 0 ≤ i, j ≤ n-1 輸出：任兩點間的最短距離矩陣A 1 for (i=0; i<n; i++) do; 2 for (j=0; j<n; j++) do; 3 A[i][j] = w[i][j]; 4 for (k=0; k<n; k++) do; 5 for (i=0; i<n; i++) do; 6 for (j=0; j<n; j++) do; 7 A[i][j] = min{A[i][j], A[i][k]+A[k][j]}

43 A+[i][j] = A+[i][j] || A+[i][k] && A+[k][j]
6.6 遞移封閉 數學上的遞移性指的是：若aRb，bRc，則aRc，其中R是某事先定義的關係。 在圖形的表示中，若將R視為「相連」的關係，則遞移性對相連關係具頗為有趣的關連。 a與b相連，b與c相連，自然a有路徑與c相連，「遞移封閉」 (transitive closure) 即欲求解： 圖形中任意兩點是否可透過遞移關係而相連。 事實上這個問題可用上節對「任意兩點間求解最短距離」的演算法來解決，因為只需求得兩點之間是否相連，所以原求最短距離的Ak可改成 A+[i][j] = A+[i][j] || A+[i][k] && A+[k][j] 之邏輯運算即得。時間複雜度亦為O(n3) 。 注意這是求解有向圖形的解法；倘若欲解遞移封閉的圖形是無向的，則可以直接利用深先或廣先搜，尋求圖形的連通部分； 若兩點在同一連通部分，勢必可有路可相連，即A+[i][j] = 1； 若兩點在不同連通部分，則兩點間無路可連，A+[i][j] = 0；而此時深先或廣先搜尋只須O(n2) 的時間。

44 6.7 拓樸序列 生活中有許多例子牽涉了事件的前後關係，例如一項工程（建造房子、生產汽車、室內裝潢…）、公文流程、在大學中選修課程、…等等，皆可能得按照某種順序方得以完成。 此時我們可利用有向圖形，用頂點代表工作項目，邊代表工作項目間的必要（先後）關係，描繪這種前後關係；這種有向圖形又稱為「頂點作業網路」 (activity-on-vertex network, AOV network) 。

45 6.7 拓樸序列 演算法6-9拓樸順序序列（topological sorting sequence） 輸入：AOV網路G = (V, E)
6.7 拓樸序列 演算法6-9拓樸順序序列（topological sorting sequence） 輸入：AOV網路G = (V, E) 輸出：G的拓樸排序序列 1 while (G中仍有頂點) 2 { if (所有的點皆有前接點) return; //此網路有迴圈，無法求解 3 任選沒有前接點之頂點v; 4 cout << v; 5 刪除v及所有自v連出的邊; 6 }