一.概述

kruskal算法是计算一副加权无向图的最小生成树的另外一种算法，它的主要思想是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入最小生成树的边构成环，直到树中含有V-1条边为止。

kruskal算法和prim算法的区别：
Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边。
kruskal算法构造最小生成树的时候也是一条边一条边地构造，但它的切分规则是不一样的：

kruskal将多个顶点看作多颗树，它每一次寻找的边会连接一片森林中的两棵树。如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，kruskal算法每一次处理都会将两棵树合并为一棵树，直到整个森林中只剩一棵树为止。

kruskal算法的实现原理：

在设计API的时候，使用了一个最小优先队列MinPriorityQueue pq存储图中所有的边，
①每次使用pq.delMin()取出权重最小的边（同时会删除pq中最小的那条边）
②并得到该边关联的两个顶点v和w，通过uf.connect(v,w)判断v和w是否已经连通：

如果连通，则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在。不做操作。
如果不连通，则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树，并把这条边加入到mst队列中，这样如果把所有的边处理完，最终mst中存储的就是最小生树的所有边。

例：

找到当前权重最小的边并删除该边，以及顶点0、7
判断两个顶点是否在同一棵树中，此时不在，则合并0和7所在的树

继续找权重最小的边，找到2、3所在边并删除该边
判断2、3是否在同一棵树上，没有，则合并2、3所在组

。。。。。

直到所有顶点都处于同一棵树中。
此时再找出权重最小的0、6所在的边并删除
判断0、6是否在同一个组，是，则不做任何处理，同理…

二.实现

public class kruskal {
    private Queue<Edge> mst; //保存最小生成树的所有边
    private uf uf; //并查集，索引代表顶点，值代表组的标识，可用conn判断顶点是否在一棵树中，使用union可以合并
    private minPriorityQueue<Edge> pq; //最小优先队列， 存储图中所有的边，按照权重进行排序，可以找到权重最小的边


    public kruskal(pathWeight g) { //参数为加权无向图
        this.mst = new LinkedList<>();
        uf = new uf(g.V());
        this.pq = new minPriorityQueue(g.E()); //最小优先队列存的是 边!
        //把图中所有的边存入pq
        for (Edge k : g.edges()) { //edges会获取所有边放入一个队列
            pq.insert(k);
        }

        //遍历pq队列，拿到权重最小的边，进行处理
        while (!pq.isEmpty() && mst.size() < g.V() - 1) {  
        //当边的数量=顶点数量-1 ，即表明最小生成树已经找到；
        //若小于 说明还没找到，还需要继续找
            //找到权重最小的边
            Edge edge = pq.delMin();
            //找到两个顶点
            int v = edge.either();
            int w = edge.other(v);

            //判断两个顶点是否在同一个组中,如果在则不做出处理；如果不在一棵树则合并这两个顶点梭子的树（组）
            if (uf.conn(v, w)) {
                continue; //在同一棵树，则不做操作，继续下一次循环
            } //如果不在同一棵树
            uf.union(v, w); //合并v、w所在的树（组）
            mst.add(edge); //让边edge进入mst最小生成树的边中
        }
    }

    //获取最小生成树中所有的边
    public Queue<Edge> edges(){
        return mst;
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89349.html

kruskal算法的实现

一.概述

kruskal算法的实现原理：

二.实现

相关推荐

分享到: