最小生成树（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 Weight0 - 1 21 - 2 25 - 3 21 - 4 24 - 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;}; 这个算法有几种变体。这取决于对边的权值排序时所使用的数据结构（如优先队列），以及图是如何表示的。