ruskal 最小生成树算法

 https://www.lanqiao.cn/problems/17138/learning/

并查集+ruskal 最小生成树算法

Kruskal 算法是一种用于在加权无向连通图中寻找最小生成树（MST）的经典算法。其核心思想是基于贪心策略，通过按边权从小到大排序并逐步选择边，确保最终形成的树满足以下条件：

1. 包含图中所有顶点（即生成树）。
2. 边权之和最小（即最小性）。
3. 不形成环路（确保是树结构）。

算法步骤

排序边：将图中所有边按权值从小到大排序。

初始化并查集：每个顶点初始时属于独立的集合，用于检测环路。

遍历选边：依次遍历排序后的边，若当前边的两个顶点不属于同一集合，则选择这条边加入最小生成树，并将两个顶点的集合合并；若属于同一集合（选边会形成环路），则跳过这条边。

终止条件：当选取的边数达到 顶点数 - 1 时，算法终止，此时已得到最小生成树。

关键数据结构：并查集（Union-Find）

作用：高效判断两个顶点是否连通（属于同一集合），并快速合并集合，确保算法时间复杂度为 O(E log E)（E 为边数）。

查找（Find）：确定顶点所在的集合根节点。

合并（merge）：将两个不同集合合并为一个集合。

package lanqiao;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {static int[] union;public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();List<int[]> list=new ArrayList();for(int i=0;i<m;i++) {int[] arr=new int[3];arr[0]=scan.nextInt();arr[1]=scan.nextInt();arr[2]=scan.nextInt();list.add(arr);}//并查集初始化union=new int[n+1];for(int i=1;i<=n;i++) {union[i]=i;}//Kruskal 最小生成树算法list.sort(((a,b)->a[2]-b[2]));int edgs=0;int max=Integer.MIN_VALUE;for(int[] arr:list) {int x=find(arr[0]);int y=find(arr[1]);if(x!=y) {edgs++;max=Math.max(max, arr[2]);merge(arr[0],arr[1]);}// 如果已经添加了n-1条边，说明已经得到了最小生成树，输出最大边权并结束程序if(edgs==n-1) {System.out.println(max);return;}}System.out.println(-1);}//查找public static int find(int x) {if(x!=union[x]) {union[x]=find(union[x]);  //路径压缩优化，使在递归过程中，//直接把arr[x]变为根结点，从而减少下一次查询的时间}return union[x];}//合并public static void merge(int x,int y) {x=find(x);y=find(y);if(x!=y) {union[x]=union[y];  //把y的根结点变成x的根结点}}}