数据结构与算法--最小生成树之Kruskal算法
上一节介绍了Prim算法，接着来看Kruskal算法。
我们知道Prim算法是从某个顶点开始，从现有树周围的所有邻边中选出权值最小的那条加入到MST中。不妨换个思路，为何不一开始就将所有边中权值最小的边取出来搭建二叉树？这里说的最小权值是全局的最小权值，而Prim说的最小权值，是已经访问过的顶点的周围的边中的最小权值，这个范围当然比全部边要小。
于是需要对边按照权值升序排列，由于每次取出的最小权值分布在图的各个地方，一开始各条边可能并不是相连的，图中就会形成多棵树。随着添加的边越来越多，两棵树合并成一棵树（用可以找到的权值最小的边连接），如此合并下去，最后只剩下一棵，这就是最小生成树。选出的边不能造成一棵树产生环，而树可以看作连通分量，不能有环就是说——处于同一个连通分量中的任意两个结点不能再将它们连通（否则必然成环）。所以我们在选出边准备连接树的时候一定要判断，选出的边如果其两个顶点处于同一个连通分量中，那么要跳过本次连接。
关键就是如何判断两个顶点是否处于同一连通分量；以及如果两个顶点不处于同一连通分量，如何将他们合并到同一连通分量中？
为此，我们要先实现一个UnionFind类来完成上述工作。
连通分量--UnionFind类的实现
package Chap7;
public class UnionFind {
// id相同的分量是连通的
private int[] id;
//连通分量的个数
private int count;
public UnionFind(int num) {
count = num;
id = new int[num];
for (int i = 0; i < num; i++) {
id[i] = i;
}
}
public int count() {
return count;
}
// 所属连通分量的id
public int find(int p) {
return id[p];
}
public void union(int p ,int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID) {
return;
}
// 将和p同一个连通分量的结点全部归到和q一个分量中，即将p所在连通分量与q所在连通分量合并。
// 反过来也可以
// if (id[i] == qID) {
// id[i] = pID;
// }
for (int i = 0; i < id.length; i++) {
if (id[i] == pID) {
id[i] = qID;
}
}
// 合并后，连通分量减少1
count--;
}
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
至关重要的就是这个id[]标识数组了。它的功能就是将处于同一连通分量的结点归并到同一个id中，也就是说如果某两个结点他们的id相同，那么他们就处于同一个连通分量中。比如id[3] = id[4]= id[6] = 8，id[2] = id[4] = id[9] = 1，那么结点3，4，6处于同一个连通分量中，结点2、4、9处于另外一个连通分量中。
find就是找到某结点所属的连通分量，如果find到两个结点属于同一个连通分量（id）,isConnected返回true。
union方法将两个不连通的分量连通。具体做法是，若结点p和q不属于同一个连通分量，则将p所在的连通通分量A的全部结点的id改成和q所在连通分量B的id一样——也就是连接p-q，连通分量A和连通分量B就将合并成一个连通分量了。
这个算法很简单，不过有待优化，可以看到每次合并分量都遍历了整个id[]，所以针对id[]进行优化。优化后id[]更像是一种树形结构，最早存在于连通分量中的为该连通分量的根结点，之后加进来的结点成为根结点的孩子结点。因为一棵树就是一个连通分量，如果两个结点往上追溯，他们有相同的根结点，说明这两个结点位于同一棵树中，也就是说这两个结点位于同一个连通分量中。
基于此思想，我们来修改下UnionFind的代码，只需变动find和union方法。
package Chap7;
public class UnionFind {
//
private int[] parentTo;
//连通分量的个数
private int count;
public UnionFind(int num) {
count = num;
parentTo = new int[num];
for (int i = 0; i < num; i++) {
parentTo[i] = i;
}
}
public int count() {
return count;
}
public int find(int p) {
// p = parentTo[p]说明到达树的根结点，返回根结点
while (p != parentTo[p]) {
p = parentTo[p];
}
return p;
}
public void union(int p,int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
// 这行的意思就是q所在连通分量和q所在连通分量合并
// 从树的角度来看，p树的根结点成为了q树根结点的孩子结点
// 反过来也可以，parentTo[qRoot] = pRoot;
parentTo[pRoot] = qRoot;
count--;
}
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
首先我们将id[]改成了parentTo[]，命名更易于理解。未优化的版本id[]存放的是各个结点所属的连通分量的标识，id表达的意义再合适不过。不过在优化的版本中，该数组是树形结构了，里面存的是某结点的父结点，用parentTo比较恰当，比如parent[3] = 4表达的意思是结点3的父结点是4。
上图的有两个连通分量，其中1和8作为根结点，可以看到根结点有p = parent[p]这一特点。它们都是初始值，从初始化代码中可以看出一开始parent[i] = i，所谓的根结点其实就是parent[i]从来没有被赋值过。
现在find(int p)方法就比较好理解了，它找到的就是p所在连通分量（树）的根结点。如果两个结点它们的根结点相同，说明处于同一个连通分量（同一棵树），这就解释了isConnected方法的实现。再看union方法，如果两个结点属于不同的树，将这两棵树连接，p树的根结点成为了q树根结点的孩子结点，其实就是两个连通分量合并成一个连通分量。和未优化版本相比，合并分量只修改了数组中一个元素的值，不用遍历整个数组了。
下图给出了分量合并的过程。
Kruskal算法实现
好了，有了这个工具，实现Kruskal算法就相当简单了。
package Chap7;
import java.util.*;
public class Kruskal {
private Queue<Edge> mst;
public Kruskal(EdgeWeightedGraph<?> graph) {
mst = new LinkedList<>();
Queue<Edge> edges = new PriorityQueue<>(graph.edges());
UnionFind uf = new UnionFind(graph.vertexNum());
// 只要mst边小于n-1就进入循环，在循环内添加一条后就变成了n-1条
while (!edges.isEmpty() && mst.size() < graph.vertexNum() -1) {
// 优先队列，删除最小权值的边
Edge edge = edges.poll();
int v = edge.either();
int w = edge.other(v);
if (uf.isConnected(v, w)) {
continue;
}
uf.union(v, w);
mst.offer(edge);
}
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return mst.stream().mapToDouble(Edge::weight).sum();
}
public static void main(String[] args) {
List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4", " v5", "v6", "v7");
int[][] edges = {{4, 5}, {4, 7}, {5, 7}, {0, 7},
{1, 5}, {0, 4}, {2, 3}, {1, 7}, {0, 2}, {1, 2},
{1, 3}, {2, 7}, {6, 2}, {3, 6}, {6, 0}, {6, 4}};
double[] weight = {0.35, 0.37, 0.28, 0.16, 0.32, 0.38, 0.17, 0.19,
0.26, 0.36, 0.29, 0.34, 0.40, 0.52, 0.58, 0.93};
EdgeWeightedGraph<String> graph = new EdgeWeightedGraph<>(vertexInfo, edges, weight);
Kruskal kruskal = new Kruskal(graph);
System.out.println("MST的所有边为：" + kruskal.edges());
System.out.println("最小成本和为：" + kruskal.weight());
}
}
代码流程比Prim算法清晰得多，理解起来也容易。无非是取出一条最小权值的边，先判断这条边中的两个顶点是否位于同一个连通分量中（同一棵树），若已连通则忽略这条边；否则将这两个顶点连通，并将这条边加入到MST。
最后注意一点，我们的Prim算法和Kruskal算法都是针对无向加权图，若是要对有向加权图处理，那被称为最小树形图，所用到的算法是朱刘算法。
by @sunhaiyu
2017.9.21
