算法描述

克鲁斯卡尔算法是一种贪心算法，因为它每一步都挑选当前最轻的边而并不知道全局路径的情况.

算法最关键的一个步骤是要判断要加入mst的顶点是否会形成回路，我们可以利用并查集的技术来做。

并查集的具体实现可参考：快速并查集

下面是对算法的一个简单描述：

这是一个非常简单易懂的算法，它面向边而不是顶点，所以在算法开始的时候，它要先找出所有的crossing edges,而为了高效的找到最轻边，用一个优先队列来维护这些crossing edges.

    /**

     * 找出所有crossing edges并加入优先队列

     */

    private void findAllCrossingEdges(){

        for(Vertex v:this.vertices) {

            for(Edge edge:v.Adj) {

                WeightedEdge we = (WeightedEdge)edge;

                this.crossingEdges.add(we);

            }

        }

    }

    private PriorityQueue<WeightedEdge> crossingEdges = new PriorityQueue<WeightedEdge>();

算法实现

下面是克鲁斯卡尔算法的一个实现：

    /**

     * 克鲁斯卡尔算法求MST

     *

     * 克鲁斯尔卡算法也是一种贪心算法(greedy algorithm)

     * 1.总是挑选最轻的边，如果这条边的两个端点没有形成回路，就将这条边加入MST

     * 2.在剩下的边中,重复1.

     *

     */

    public void kruskalMST() {

        resetMemo();

        //找出所有crossing edges

        findAllCrossingEdges();

        //初始化并查集

        FastUnionFind uf = new FastUnionFind(vertexCount());

        //算法用贪心策略，每一步都挑选最轻的边来加入mst

        //需要注意的是，在加入mst之前要考察边的两端顶点是否形成环路

        while (!this.crossingEdges.isEmpty()) {

            //最轻边

            WeightedEdge edge = crossingEdges.poll();

            //如果点src和点to没有形成环

            if(!uf.isConnected(edge.src,edge.to)){

                //将src和to连通

                uf.union(edge.src,edge.to);

                //将最轻边加入mst

                mst.offer(edge);

                //更新mst的权重

                mstWeight += edge.weight;

            }

        }

    }

时间复杂度

算法需要对所有边E 进行访问，这步操作耗时O(E )

将边入队和出队的操作耗时O(logE).

由于假设图是连通的,并查判断回路操作耗时O(logE)

所以整体耗时O(ElogE ).

由于 |E| < V*V,所以logE = 2logV，则可将算法复杂度写为O(ElogV).