Kruskal算法

Kruskal算法是在数据结构书中就已经知晓的一种算法，是生成最小生成树思路中的加边法。

算法的基本思想

给定无向连通带权图G=(V,E)，生成最小生成树的基本思想是：

• 首先将G的n个顶点看成n个孤立的连通分支，将所有的边按权从小到大排序
• 然后从第一条边开始，依边权递增的顺序查看每条边，并按照上述方法连接两个不同的连通分支
• 党察看到第k条边（v,w）时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用链（v,w）将T1和T2连接成一个连通分支，然后继续查看第K+1条边
• 如果端点V和w在当前的同一连通分支中，就直接再查看第k+1条边
• 等到只剩下一个连通分支为止，这个连通分支就是G的一棵最小生成树

问题

• 我们的这个图 现在该怎么存
• 我们怎么决定两个点之间已经有了联通路
• 我们怎么回溯返回这个已经创建好的最小生成树

我的手写笔记

我的学习方法

1. 自己看书
2. 看视频

P55-图-6.Kruskal算法_哔哩哔哩_bilibili 这个老师的视频简单易懂

代码

边结构体的代码

package passage04;

public class EdgeNode {
    //这里为了偷懒 都是用的是整数型
    //weight表示边的权重
    int weight;
    //该边的一个节点
    int u;
    //v表示该边的另一个节点
    int v;

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getU() {
        return u;
    }

    public void setU(int u) {
        this.u = u;
    }

    public int getV() {
        return v;
    }

    public void setV(int v) {
        this.v = v;
    }

    public EdgeNode(int u,int v,int weight) {
        this.weight = weight;
        this.u = u;
        this.v = v;
    }

    public EdgeNode() {
    }

    @Override
    public String toString() {
        return "EdgeNode{" +
                "weight=" + weight +
                ", u=" + u +
                ", v=" + v +
                '}';
    }
}

Kruskal代码

package passage04;

//这是一个最小生成树问题
public class MyKruskal {
    //这里我们使用num来表示有几个结点
    private int num;

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    //这里我们需要的是一个排序
    public void edgeSort(EdgeNode[] A){
        //使用的是一个冒泡排序
        for(int i=A.length-1;i>=0;i--){
            for (int j=0;j<i;j++){
                if (A[j].weight>A[j+1].weight){
                    //找到 交换
                    EdgeNode temp = A[j];
                    A[j] = A[j+1];
                    A[j+1] = temp;

                }
            }
        }
    }

    //这里我们使用树来存放我们已经联结好的图
    //首先我们需要一个寻找根节点的算法
    //p表示我们想要查找的根节
    //V表示我们的并查集
    int getRoot(int p,int[] V){
        while (V[p] != p){
            p = V[p];
        }
        return p;
    }
    //合并两个树的方法
    //P Q表示要合并的两个节点
    void mergeNode(int P,int Q,int[] V){
        //这里我规定 我要让标号小的数做父节点
        if (P > Q){
            V[P] = Q;
        }else {
            V[Q] = P;
        }
    }

    //Kruskal算法核心
    public int Kruskal(EdgeNode[] A){
        int sum = 0;
        //生成一个合并集
        int[] V = new int[num];
        //我们规定 如果一个节点是根节点 那么他就存储自己
        for (int i=0;i<num;i++){
            V[i] = i;
        }
        //给我们的边的数列排序
        edgeSort(A);
        //开始找边看看是否合适
        for (EdgeNode edgeNode : A) {

            //从最小的边开始 向我们的并合集中存数据
            int u = edgeNode.getU();
            int v = edgeNode.getV();
            int P = getRoot(u, V);
            int Q = getRoot(v, V);
            //如果两个点的根节点不同 那他们就不再一棵数树上 就要合并
            if (P!=Q){
                sum = sum + edgeNode.weight;
                mergeNode(P,Q,V);
                //复盘 联结节点
                System.out.println("选择双向边从"+edgeNode.u+"到"+edgeNode.v+"权重为"+edgeNode.weight);
            }
        }
        return sum;
    }


}

测试代码

package passage04;

public class MyKruskalTest {
    public static void main(String[] args) {
        //创建一个边的集合
        EdgeNode node1 = new EdgeNode(0, 1, 1);
        EdgeNode node2 = new EdgeNode(0, 2, 5);
        EdgeNode node3 = new EdgeNode(0, 3, 6);
        EdgeNode node4 = new EdgeNode(1, 2, 8);
        EdgeNode node5 = new EdgeNode(1, 4, 4);
        EdgeNode node6 = new EdgeNode(2, 4, 2);
        EdgeNode node7 = new EdgeNode(2, 3, 7);
        EdgeNode node8 = new EdgeNode(4, 5, 9);
        EdgeNode node9 = new EdgeNode(3, 5, 3);

        EdgeNode[] A = new EdgeNode[]{node1,node2,node3,node4,node5,node6,node7,node8,node9};
        MyKruskal myKruskal = new MyKruskal();
        myKruskal.setNum(6);
        int kruskal = myKruskal.Kruskal(A);
        System.out.println(kruskal);

    }
}

测试结果

选择双向边从0到1权重为1
选择双向边从2到4权重为2
选择双向边从3到5权重为3
选择双向边从1到4权重为4
选择双向边从0到3权重为6
    16

Donate