圖上的邊除了表示兩個頂點相連，還可以帶著一個數字，稱為權重（weight）。權重可以是造價、距離、時間或費用，帶有權重的圖就是加權圖（weighted graph）。

用同一張加權圖，可以回答兩個問題。假設圖上的 6 個頂點是 6 間機房，邊是可以拉網路線的路徑，數字是每條線的造價：

• 要用最少的總造價，挑幾條線把 6 間機房全部連起來，該挑哪幾條？這是最小成本生成樹。
• 資料從機房 A 出發，傳到其他每間機房，走哪條路的成本最低？這是最短路徑。

數字也可以代表路程或延遲。以下範例使用連通的無向圖，權重互不相同，也沒有負數。n 代表頂點數，e 代表邊數。

加權圖怎麼存

相鄰矩陣原本用 1 表示有邊，加上權重後，格子改放權重。沒有邊的格子放 ∞，避免把 0 誤當成最便宜的邊（實際寫程式時，用一個夠大的數代替）；對角線放 0，表示自己到自己不用花成本。相鄰串列的每個節點，除了記相鄰頂點，再多記一個權重。

最小成本生成樹

生成樹是連通圖的一個子圖：它包含全部 n 個頂點，而且本身是一棵樹，所以剛好有 n − 1 條邊。

一張圖可以有很多棵生成樹。在加權圖裡，邊的權重總和最小的那一棵，稱為最小成本生成樹。範例有 6 個頂點，要挑 5 條邊，讓總造價最小。權重互不相同時，最小成本生成樹只有一棵；權重有相同時，可能有好幾棵。

常見的做法有兩種：Prim 演算法和 Kruskal 演算法。它們選邊的過程不同，但會得到同一棵樹。

Prim 演算法：從一個頂點慢慢長大

Prim 演算法的規則是：

1. 任選一個頂點放進樹裡（例如 A）。
2. 在所有「一端在樹內、一端在樹外」的邊裡，挑權重最小的一條，把它和樹外那個頂點一起加進樹。這些邊稱為候選邊。
3. 重複第 2 步，直到所有頂點都在樹裡。

要注意步驟 4：A-F(14) 已經不在候選邊裡了，因為 A 和 F 都在樹內，再加這條邊會形成環（A、C、F 繞成一圈）。每一步只看「一端在樹內、一端在樹外」的邊，就不會形成環。

Kruskal 演算法：由小到大挑邊，不能形成環

Kruskal 演算法的規則是：

1. 把全部的邊，依權重由小到大排好。
2. 依序檢查每一條邊：如果它的兩端在不同的連通元件（互相走得到的一群頂點），就加入；如果兩端已經在同一個連通元件，加進去會形成環，就跳過。
3. 選到 n − 1 條邊就結束。

這裡的連通元件，指的是目前已經選出的邊所形成的：一開始還沒選任何邊，每個頂點各自是一個連通元件；每加入一條邊，就把兩個連通元件接在一起。

排好的邊依序是：C-F(2)、D-E(6)、A-B(7)、A-C(9)、B-C(10)、C-D(11)、E-F(12)、A-F(14)、B-D(15)。

步驟 6 之後已經選了 5 條邊，也就是 n − 1 條，所以結束，後面的 E-F(12)、A-F(14)、B-D(15) 不用再看。總成本是 2 + 6 + 7 + 9 + 11 = 35。

兩種做法的比較

Prim 的選邊順序是 A-B、A-C、C-F、C-D、D-E，Kruskal 是 C-F、D-E、A-B、A-C、C-D，順序完全不同，但選出來的 5 條邊一模一樣，總成本都是 35。

• Prim 是從一個頂點開始，讓同一棵樹一路長大。
• Kruskal 一開始每個頂點各自是一塊，每加入一條邊，就把兩個連通元件接在一起。過程中選到的邊形成一座森林（沒有環的無向圖），到最後才合成一棵樹。

Kruskal 若能有效率地判斷與合併連通元件，主要時間花在排序 e 條邊，總時間是 O(e log e)。

Prim 要做 n − 1 輪。用相鄰矩陣時，替每個樹外頂點記錄「目前接到樹的最小邊權重」，每輪掃一遍挑出最小的，再用剛加入的頂點那一列更新紀錄，每輪花 O(n)，總時間是 O(n²)。如果用相鄰串列，再用最小累堆（樹根存放最小值）挑出最小者，可以達到 O(e log n)。

最短路徑：Dijkstra 演算法

加權圖裡，一條路徑的長度是路徑上所有邊的權重總和。未加權圖用邊數計算路徑長度，相當於每條邊的權重都是 1，這時用廣度優先搜尋（BFS，一層一層往外拜訪頂點）就能找到最短路徑。

最短路徑問題是：給定一個起點（例如 A），求它到其他每個頂點的最短路徑。Dijkstra 演算法的規則是：

1. 起點的距離設為 0，其他頂點設為 ∞，所有頂點都還沒「確定」。
2. 從還沒確定的頂點中，挑目前距離最小的頂點 u，把它確定下來，它的最短距離不會再改變。
3. 看 u 的每個還沒確定的相鄰頂點 v：如果「起點到 u 的距離 + 邊 (u, v) 的權重」比 v 目前的距離小，就把 v 的距離改成這個值，並記下 v 的前一個頂點是 u。
4. 重複第 2、3 步，直到所有頂點都確定。

下表每一列是挑出一個頂點後，各頂點目前的距離（A 的距離一直是 0，所以省略）：

A 到 B、C、D、E、F 的最短距離，依序是 7、9、20、23、11。要知道實際怎麼走，就順著「前一個頂點」往回找：E 的前一個頂點是 F，F 的前一個是 C，C 的前一個是 A，所以最短路徑是 A → C → F → E，長度 9 + 2 + 12 = 23。如果直接走 A → F → E，長度是 14 + 12 = 26，反而比較遠。

為什麼每次挑目前距離最小的頂點，就能把它確定？因為其他還沒確定的頂點，目前距離都不小於它；在權重不是負數的前提下，經由那些頂點繞過來，也不會得到更短的路徑，所以它的距離不會再變小。如果有負權重，這個推論就不成立，所以 Dijkstra 演算法只能用在沒有負權重的圖。

時間方面，每次用陣列掃描找距離最小的頂點要 O(n)，最多做 n 次；加上更新相鄰頂點的距離，用相鄰矩陣時總時間是 O(n²)。如果用相鄰串列加上累堆來挑最小的，可以降到 O(e log n)。

最小成本生成樹和最短路徑，差在哪裡

同一張圖，兩個問題的答案並不一樣：

兩棵樹只差一條邊：最小成本生成樹用便宜的 D-E(6)，最短路徑卻用 E-F(12)。生成樹在乎的是整體最省，所以選 D-E；最短路徑只在乎從 A 出發的距離，到 E 走 F 比較近。所以最小成本生成樹上兩個頂點之間的路，不一定是最短路徑。

Prim 和 Dijkstra 的過程很像：都是每次從還沒加入的頂點中，挑一個「最好」的，再往外長。差別在「最好」的標準：Prim 看的是連到現有那棵樹的單一邊權重，Dijkstra 看的是從起點走過來的總距離。

小結

加權圖的邊帶著權重，相鄰矩陣的格子改放權重（沒有邊放 ∞），相鄰串列的節點多記一個權重。最小成本生成樹，是用最少的總權重把所有頂點連起來的那棵生成樹：Prim 從一個頂點長大，每次挑一端在樹內、一端在樹外的最小邊；Kruskal 把邊由小到大檢查，兩端已在同一個連通元件的就跳過，兩者會得到同一棵樹。最短路徑則是求起點到每個頂點的最短距離：Dijkstra 每次確定距離最小的頂點，再用它去更新相鄰頂點的距離。兩個問題要的東西不同，答案也可能不同。

今日重點：

• 加權圖的邊帶著權重；相鄰矩陣放權重、沒有邊放 ∞（對角線放 0），相鄰串列的節點多記一個權重。
• 生成樹是包含全部 n 個頂點的樹，剛好 n − 1 條邊；權重總和最小的那棵是最小成本生成樹。
• Prim：從一個頂點開始，每次挑一端在樹內、一端在樹外的最小邊。
• Kruskal：邊由小到大檢查，兩端在不同的連通元件才加入，已在同一個連通元件的跳過，選到 n − 1 條邊結束。
• 權重互不相同時，最小成本生成樹只有一棵，Prim 和 Kruskal 會選出同一棵，只是順序不同。
• 加權圖的路徑長度是邊的權重總和；Dijkstra 每次確定距離最小的頂點，並更新它相鄰頂點的距離，權重不能是負數。
• 最小成本生成樹求的是整體最省，最短路徑求的是從起點出發的距離最短，兩者用到的邊可能不同。

下一篇開始介紹排序：一副亂序的撲克牌，你會怎麼把它排好？電腦也有不同的排序方法，我們會比較它們的做法與執行時間。