首页 > 代码库 > 算法8-4:Kruskal算法

算法8-4:Kruskal算法

Kruskal算法用于计算一个图的最小生成树。这个算法的步骤如下:

  1. 按照边的权重从小到达进行排序

  2. 依次将每条边增加到最小生成树中,除非这条边会造成回路


实现思路


第一个步骤需要对边进行排序,排序方法在之前的章节中已经介绍了很多,可以使用优先级队列进行实现,也可以使用归并排序进行实现,这里采用归并排序。


第二个步骤需要判断是否会造成回路。如果增加一条边会形成回路,那么这条边在增加之前,它两端的顶点必定是能够连通的。因此,在算法中使用并查集实现高效的判断。


代码


import java.util.LinkedList;
import java.util.Queue;
 
public class KruskalMST {
    private Queue<Edge> mst = new LinkedList<Edge>();
 
    public KruskalMST(EdgeWeightedGraph G) {
        // 先对边进行排序
        Edge[] edges = new Edge[G.E()];
        int i = 0;
        for (Edge e : G.edges()) {
            edges[i] = e;
            i++;
        }
        MergeSort.sort(edges);
 
        // 使用并查集判断顶点是否连接
        UnionFind uf = new UnionFind(G.V());
        for (Edge e : edges) {
            int v = e.either();
            int w = e.other(v);
            if (!uf.connected(v, w)) {
                uf.union(v, w);
                mst.add(e);
            }
        }
    }
 
    public Iterable<Edge> edges() {
        return mst;
    }
 
    public double weight() {
        double result = 0;
        for (Edge e : mst) {
            result += e.weight();
        }
        return result;
    }
}


复杂度


上面的代码复杂度和图中边的数量有关,最坏情况下的复杂度为E logE。