介绍构造最小生成树还有一种算法，即 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 list<edge> 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; } }}
三、测试绿色为输入，白色为输出。
以上就是java如何实现kruskal算法的详细内容。