7.5 擴張樹 (Spanning Tree) 一個無向相連圖 G 的子圖 G’ 如果可用最少的邊來連接G 的 擴張樹的特徵 非唯一 任兩頂點間均有路徑相通 共有 n-1 個邊，再加任何原圖 G 的其他非 G’的邊都會形成迴路 1 1

擴張樹範例 1 2 2

擴張樹範例 2 這部份沒有範例程式，大家可以想想看要怎麼做 以 DFS 拜訪頂點所得之擴張樹，但這裡與 7.4 不同的是還須處理邊 以 BFS 拜訪頂點所得之擴張樹，但這裡與 7.4 不同的是還須處理邊 3 3

網路 (Network) 與 最少成本擴張樹 (Minimum Cost Spanning Tree) 如果在圖形 G 的邊上賦予成本 (cost，又稱權重)，得到的結果圖形就稱為網路 (Network) 這個權重可以用之前的 2 維相鄰矩陣來存放 代表兩頂點 x, y 不相鄰的方式有 2 種 adjmatrix[x][y] = 0 ：適用於 DFS, BFS 等應用 adjmatrix[x][y] = ∞：適用於最少成本擴張樹 這個權重可用來代表 地圖上兩點間的距離、兩點間的行車時間、兩點間的成本… 網路 G 的最少成本擴張樹是 G 的所有擴張樹中其邊的成本總和最低者 最少成本擴張樹非唯一 最少成本擴張樹任兩點 x, y 間只有一條路徑，且此路徑之所有邊成本和不一定是 x, y 間之最低成本 4

最小成本擴張樹範例 5 5

7.5.1 最小成本擴張樹- P 氏法 (Prim’s Method) P 氏法求 G=(V,E) 之最小成本擴張樹 以頂點為導向，先確定要加進來的頂點，再由點找邊 將所有頂點切割成 X, Y 兩個集合， X 用來代表還未加入最小成本擴 張樹的頂點之集合， Y 用來代表已加入最少成本擴張樹的頂點之集 合，令 T 代表最小成本擴張樹 (含頂點及邊)， P 氏法會將頂點一 個一個由集合 X 搬到 Y，直到 X 為空集合為止 1.令 X=V，Y=Φ，T=Φ (T 為空樹)。 2.從 X 中任選一個頂點 x，將之從 X 搬移到 Y，並將 x 加入 T。 3.重覆執行步驟 4、5，一直到 X 為空集合為止 4. 從所有邊的集合 E 中找出一條連接 X 和 Y 的最少成本邊 (x,y)，其中 x ∈ X，y ∈ Y，且邊(x,y)加到 T 不會造成迴路。 5. 將頂點 x 自 X 搬移到 Y，並將頂點 x 與 邊(x,y)加入樹 T。 6. 輸出最小成本擴張樹 T 及總成本。   範例：上一頁講義，假設步驟 2 選到的頂點為 a 6 6

練習 由 A 開始求 最小成本擴張樹 參考：http://students.ceid.upatras.gr/~papagel/project/prim.htm 7

7.5.2 最小成本擴張樹- K 氏法 (Kruskal’s Method) K 氏法求 G=(V,E) 之最小成本擴張樹 以邊為導向，慢慢將不會造成迴路且成本最小的邊加入最小成本 擴張樹T，直到 T 的邊的個數為 n -1 1.令 T=Φ (T 為空樹)。 2.重覆執行步驟 3、4，一直到 T 的邊總數為 n -1 3.從 E 中選取成本最小的邊(x ,y)。 4.如果將 (x,y) 加到 T 不會造成迴路，則 { 從 E 中刪除邊 (x,y) ， 將邊(x,y) 加到 T 。 } 否則 { 從 E 中刪除邊 (x,y) } 5. 輸出最小成本擴張樹 T 及總成本。   範例：如 P 氏法 2 個範例，再用 K 氏法做一遍 (ch7_mincostspanningtree.java，有修正過) 跳過 7.5.3 參考：http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

7.6 最短路徑問題 (shortest path problem) 求得網路 G=(V,E) 的最小成本擴張樹並無法解決以下問題 單一頂點到其他頂點的最短距離(或最小成本)為何 G 中任兩頂點間的最短距離(或最小成本)為何 本節改以有向圖為範例 9 9

7.6.1單一頂點到其他頂點的最短距離 Dijkstra’s Algorithm：使用到 3 個陣列 cost[n,n]：兩頂點間相鄰成本陣列成本 一開始對所有頂點 i， cost[i, i] = 0 visited[n]：用來對已拜訪過的頂點做 “已拜訪” 的記號 一開始對所有頂點 i， visited[i] = false dist[n] ：存放出發頂點 s 到所有頂點到目前為止之最短距離 一開始 dist[i] = cost[s][i] (其中dist[s] = cost[s,s] = 0) 變數 vcount 用來代表到目前為止拜訪過的頂點個數 10 10

判斷加入 x 以後是否由 s 到 x 再到 i 的距離會比現有最短距離還小 ∈ ∉ visited[s] 判斷加入 x 以後是否由 s 到 x 再到 i 的距離會比現有最短距離還小 11

單一頂點到其他頂點的最短距離範例 12 12

練習：將 ch7_shortestpath.java 改為請使用者輸入出發的頂點 13 13 練習：將 ch7_shortestpath.java 改為請使用者輸入出發的頂點

練習 14 14

練習參考解答 頂點0到其餘頂點之最短距離選取過程 頂點0到其餘頂點之最短路徑和距離 15 15

7.6.2 任兩頂點間的最短距離 (Floyd’s Algorithm) 可用 7.6.1 的方法，輪流將各頂點設為出發頂點求得，但 速度太慢 此節介紹可同時求得任兩頂點間的最短距離的方法 資料結構 cost[n,n]：兩頂點間相鄰成本陣列成本 視題目有沒有要求一定要走出去，決定要不要 一開始對所有頂點 i， cost[i, i] = 0 C[n][n]：存放到目前為止兩頂點間的最短距離 C[n][n] 會慢慢改變，假設其改變順序為 C0[n][n], C1[n][n], …, Cn-1[n][n] 令各 Ck [i][j] 代表由頂點 i 到頂點 j 且所經過之頂點不超過 k 的所有路 徑之最短距離，則當 k=n-1 時， Cn-1 [i][j] 代表由頂點 i 到頂點 j 且所 經過之頂點不超過 n-1 的所有路徑之最短距離，也就是頂點 i 到頂點 j 的最短距離 (因為頂點編號是由 0 到 n-1) 課本 p.7-102 要訂正 16

演算法 (ch7_allpath.java) 步驟 令 C-1[i][j]=cost[i][j] 對所有 i, j for (k = 0; k <= n-1, k++) { Ck[i][j]= min｛Ck-1[i][j] , Ck-1[i][k] + Ck-1[k][j] } } ∈ ∉ 17

範例 題目有要求一定要走出去 18

練習 題目沒要求一定要走出去 19

7.7 工作網路與拓樸排序(Topological Sort) 頂點工作網路(Activity On Vertex Network)，簡稱 AOV 網路 是一個有向圖 以頂點來代表工作項目 邊則用來代表工作被執行的優先順序 此圖不可有迴路 如果存在邊 <i, j>，表示 i 工作須比 j 工作早完成 (優先) 拓樸排序：維持 AOV 網路上各頂點之先後關係並依工作項 目完成之先後加以排序 非唯一 20

拓樸排序範例 拓樸排序結果為 A、B、C、D、E 或 B、A、C、D、E。 拓樸排序結果為 1、0、2、3、4 、5、6、7 或 0、1、2、3、4 、6、5、7 或 1、0、3、2、4 、5、6、7 或 0、1、3、2、4 、5、6、7 或 1、0、2、3、4 、6、5、7 或 … 共 8 組 定義：拓樸排序的長度 為該排序所有路徑 之長度中的最大值 21

拓樸排序程式 (ch7_topologicalsort.java) 當 AOV 網路尚有頂點，重複執行 2 2. 任意挑選一個 沒有先行者 (predecessor) 的頂點 x ，從 AOV 網路中刪除 x 以及從 x 出發的邊，輸出 x 22

以佇列實作拓樸排序程式(作業) ch7_topologicalsort.java 是依照頂點的號碼來找到一組 拓樸排 序，以佇列實作可找到長度為最小的拓樸排序 (p.21) 令 counter =0 ; // 這用來紀錄已加入拓樸排序的頂點數目 先計算每一個頂點的入分支度 將入分支度為 0 的所有頂點加入一個 佇列 q 執行以下動作，直到佇列為空 由佇列取出最前面的頂點 x ，並輸出 x counter++; 對所有 x 可連接到的頂點 y ，如果 y 還沒被輸出，進行以下動作： 將 y 的入分支度減 1 ，如果 y 的入分支度成為 0 ，則將 y 加入佇列 q 4. 如果 counter < n ，表示該 有向圖 有迴路

ch7_mincostspanningtree.java 的問題 > 演算法是正確，但是 cycle( ) 的判斷有問題，以下例來看： 將 (0,1), (3,4) 加入 T 後，接下來 cycle( ) 會 判斷 (0,3) 造成迴路， 再判斷 (1,3) 也造成迴路，於是選擇 (4,5) 結果是錯的

修正 ch7_mincostspanningtree.java 中 cycle 的做法 概念：於運算過程中，維護各相連子圖的代表頂點，如果 要加進來的邊的兩個頂點所在之相連子圖的代表頂點相同 ，則表示有迴路 作法：以相連子圖所有頂點中數字最小的頂點代表作為該 相連子圖之代表頂點 設計一個陣列 represent[n]，此陣列用來代表各頂點目前所屬 相連子圖的代表頂點，由於剛開始的時候，各頂點都沒有加入 represent[i] 的值就是 i 最小成本邊選好以後，假設該邊為 (x,y) 如果 represent[x] = represent[y]，則加入此邊會造成迴路 如果 represent[x] ≠ represent[y]，則加入此邊不會造成迴路，而可連 接原來不相鄰的子圖 假設 represent[x] 與 represent[y] 的較小值為 z1 、較大值為 z2，則檢查所 有 represent[i] 的值，如果其值為 z2，就將之改為 z1

範例 Step Rep[0] Rep[1] Rep[2] Rep[3] Rep[4] Rep[5] Rep[6] 1 2 3 4 5 6

作業 3 完成 最小成本擴張樹- P 氏法 此題請由檔案輸入該網路的成本矩陣 2. 完成最小成本擴張樹- K 氏法正確的 cycle 方法 (投影片第 25 頁) 3. ch7_topologicalsort.java 是依照頂點的號碼來找到一組 拓樸排序，本 題要求如第 23 頁的演算法改寫 ch7_topologicalsort.java。 此題請由檔案輸入該有向圖的相鄰矩陣。 27