介绍

构造最小生成树还有一种算法，即 Kruskal 算法：设图 G=（V，E）是无向连通带权图，V={ 1,2，...n} ; 设最小生成树 T=(V，TE)，该树的初始状态只有 n 个节点而无边的非连通图T=(V,{ } ),Kruskal 算法将这n 个节点看成 n 个孤立的连通分支。它首先将所有边都按权值从小到大排序，然后值要在 T 中选的边数不到 n-1,就做这样贪心选择：在边集 E 中选择权值最小的边(i,j),如果将边(i,j)加入集合 TE 中不产生回路，则将边(i,j)加入边集 TE 中，即用边(i，j)将这两个分支合并成一个连通分支；否则继续选择下一条最短边。把边(i,j)从集合 E 中删去，继续上面的贪心选择，直到 T 中的所有节点都在同一个连通分支上为止。此时，选取的 n-1 条边恰好构成图 G 的一棵最小生成树 T。

Kruskal 算法用一种非常聪明的方法，就是运用集合避圈；如果所选择加入边的起点和终点都在 T 集合中，就可以断定会形成回路，变的两个节点不能属于同一个集合。

算法步骤

1 初始化。将所有边都按权值从小到大排序，将每个节点集合号都初始化为自身编号。

2 按排序后的顺序选择权值最小的边（u,v）。

3 如果节点 u 和 v 属于两个不同的连通分支，则将边(u,v)加入边集 TE 中，并将两个连通分支合并。

4 如果选取的边数小于 n-1,则转向步骤2，否则算法结束。

一、构建后的图

二、代码

package graph.kruskal;
    
 
import java.util.ArrayList;
    
import java.util.Collections;
    
import java.util.List;
    
import java.util.Scanner;

 
public class Kruskal {
    
    static final int N = 100;
    
    static int fa[] = new int[N];
    
    static int n;
    
    static int m;
    
 
    static Edge e[] = new Edge[N * N];
    
    static ListEdge>
     edgeList = new ArrayList();

 
    static {
    
        for (int i = 0;
     i  e.length;
 i++) {
    
            e[i] = new Edge();

        }

    }

 
    // 初始化集合号为自身
    static void Init(int n) {
    
        for (int i = 1;
     i = n;
     i++)
            fa[i] = i;

    }

 
    // 合并
    static int Merge(int a, int b) {
    
        int p = fa[a];
    
        int q = fa[b];
    
        if (p == q) return 0;
    
        for (int i = 1;
     i = n;
 i++) {
     // 检查所有结点，把集合号是 q 的改为 p
            if (fa[i] == q)
                fa[i] = p;
 // a 的集合号赋值给 b 集合号
        }
    
        return 1;

    }

 
    // 求最小生成树
    static int Kruskal(int n) {
    
        int ans = 0;
    
        Collections.sort(edgeList);
    
        for (int i = 0;
     i  m;
 i++)
            if (Merge(edgeList.get(i).u, edgeList.get(i).v) == 1) {
    
                ans += edgeList.get(i).w;
    
                n--;
    
                if (n == 1)//n-1次合并算法结束
                    return ans;

            }
    
        return 0;

    }

 
    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
    
        n = scanner.nextInt();
    
        m = scanner.nextInt();
    
        Init(n);
    
        for (int i = 1;
     i = m;
 i++) {
    
            e[i].u = scanner.nextInt();
    
            e[i].v = scanner.nextInt();
    
            e[i].w = scanner.nextInt();
    
            edgeList.add(e[i]);

        }
    
        System.out.println("最小的花费是：" + Kruskal(n));

    }

}

 
class Edge implements Comparable {
    
    int u;
    
    int w;
    
    int v;

 
    @Override
    public int compareTo(Object o) {
    
        if (this.w >
 ((Edge) o).w) {
    
            return 1;

        }
 else if (this.w == ((Edge) o).w) {
    
            return 0;

        }
 else {
    
            return -1;

        }

    }

}
    

三、测试

绿色为输入，白色为输出。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！