介绍
构造最小生成树还有一种算法,即 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 中,并将两个连通分支合并。
FilePond 是一个 JavaScript 文件上传库,支持通过拖拽、粘贴和 API 方式处理文件、目录、URL 和 Data URI。它包含内置的图像优化功能、异步分块上传功能,并提供了适用于 React、Vue、Angular 和 Svelte 的适配器。
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 ((Edge) o).w) {
return 1;
} else if (this.w == ((Edge) o).w) {
return 0;
} else {
return -1;
}
}
}</edge>
三、测试
绿色为输入,白色为输出。

Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南










