學習JavaScript數據結構與算法（第2版）：9.6 最小生成樹_Loiane Grone

最小生成樹（MST）問題是網絡設計中常見的問題。想像一下，你的公司有幾間辦公室，要以最低的成本實現辦公室電話線路相互連通，以節省資金，最好的辦法是什麼？

這也可以應用於島橋問題。設想你要在n個島嶼之間建造橋樑，想用最低的成本實現所有島嶼相互連通。

這兩個問題都可以用MST算法來解決，其中的辦公室或者島嶼可以表示為圖中的一個頂點，邊代表成本。這裡我們有一個圖的例子，其中較粗的邊是一個MST的解決方案。

本節我們將學習兩種主要的求最小生成樹的算法：Prim算法和Kruskal算法。

9.6.1　Prim算法

Prim算法是一種求解加權無向連通圖的MST問題的貪心算法。它能找出一個邊的子集，使得其構成的樹包含圖中所有頂點，且邊的權值之和最小。

現在，通過下面的代碼來看看Prim算法是如何工作的：

this.prim = function {
  var parent = ,
    key = ,
    visited = ;
    length = this.graph.length,
    i;

  for (i = 0; i < length; i++) { //{1}
    key[i] = INF;
    visited[i] = false;
  }

  key[0] = 0; //{2}
  parent[0] = -1;

  for (i = 0; i < length-1; i++) { //{3}
    var u = minKey(key, visited); //{4}
    visited[u] = true; //{5}

    for (var v = 0; v < length; v++) {
      if (this.graph[u][v] && visited[v] == false
      && this.graph[u][v] < key[v]) { //{6}
      parent[v] = u; //{7}
      key[v] = this.graph[u][v]; //{8}
      }
    }
  }
  return parent; //{9}
};

下面是對算法過程的描述。

行{1}：首先，把所有頂點（key）初始化為無限大（JavaScript最大的數INF = Number.MAX_SAFE_INTEGER），visited初始化為false。
行{2}：其次，選擇第一個key作為第一個頂點，同時，因為第一個頂點總是MST的根節點，所以parent[0] = -1。
行{3}：然後，對所有頂點求MST。
行{4}：從未處理的頂點集合中選出key值最小的頂點（與Dijkstra算法中使用的函數一樣，只是名字不同）。
行{5}：把選出的頂點標為visited，以免重複計算。
行{6}：如果得到更小的權值，則保存MST路徑（parent，行{7}）並更新其權值（行{8}）。
行{9}：處理完所有頂點後，返回包含MST的結果。

　比較Prim算法和Dijkstra算法，我們會發現除了行{7}和行{8}之外，兩者非常相似。行{7}用parent數組保存MST的結果。行{8}用key數組保存權值最小的邊，而在Dijkstra算法中，用dist數組保存距離。我們可以修改Dijkstra算法，加入parent數組。這樣，就可以在求出距離的同時得到路徑。

對如下的圖執行以上算法：

var graph = [[0, 2, 4, 0, 0, 0],
             [2, 0, 2, 4, 2, 0],
             [4, 2, 0, 0, 3, 0],
             [0, 4, 0, 0, 3, 2],
             [0, 2, 3, 3, 0, 2],
             [0, 0, 0, 2, 2, 0]];

我們會得到如下輸出：

Edge    Weight
0 - 1   2
1 - 2   2
5 - 3   2
1 - 4   2
4 - 5   2

9.6.2　Kruskal算法

和Prim算法類似，Kruskal算法也是一種求加權無向連通圖的MST的貪心算法。

現在，通過下面的代碼來看看Kruskal算法是如何工作的：

this.kruskal = function {
  var length = this.graph.length,
  parent = , cost,
  ne = 0, a, b, u, v, i, j, min;
  cost = initializeCost; //{1}

  while (ne < length-1) { //{2}
    for (i = 0, min = INF; i < length; i++) { //{3}
      for (j = 0; j < length; j++) {
        if (cost[i][j] < min) {
          min = cost[i][j];
          u = i;
          v = j;
        }
      }
    }

    u = find(u, parent); //{4}
    v = find(v, parent); //{5}

    if (union(u, v, parent)) { //{6}
      ne++;
    }

    cost[u][v] = cost[v][u] = INF; //{7}
  }
  return parent;
}

下面是對算法過程的描述。

行{1}：首先，把鄰接矩陣的值複製到cost數組，以方便修改且可以保留原始值行{7}。
行{2}：當MST的邊數小於頂點總數減1時。
行{3}：找出權值最小的邊。
行{4}和行{5}：檢查MST中是否已存在這條邊，以避免環路。
行{6}：如果u和v是不同的邊，則將其加入MST。
行{7}：從列表中移除這些邊，以免重複計算。
行{8}：返回MST。

下面是find函數的定義。它能防止MST出現環路：

var find = function(i, parent) {
  while (parent[i]) {
    i = parent[i];
  }
  return i;
};

union函數的定義如下：

var union = function(i, j, parent) {
  if (i != j) {
    parent[j] = i;
    return true;
  }
  return false;
};

這個算法有幾種變體。這取決於對邊的權值排序時所使用的數據結構（如優先隊列），以及圖是如何表示的。

9.6.1 Prim算法

9.6.2 Kruskal算法

9.6.1　Prim算法

9.6.2　Kruskal算法