《最小生成树算法详解：Kruskal的优雅实现》

前置知识和本篇介绍

前置知识：数据结构-优先级队列，数据结构-并查集。
Kruskal算法不需要建图，因此不会建图的模板也没事。

本篇介绍一最小生成树的概念和Kruskal算法。有关prim算法（另一种最小生成树的算法），以及更多优化技巧和刷题本篇不会提及。

《最小生成树算法详解：Kruskal的优雅实现》

一. 引言

什么是最小生成树（MST）？
简要介绍 Kruskal 算法的核心思想和优势。

一家通信公司试图建立其各个计算机中心的通信联系。
它当然可以通过租用电话线连接任意之间的一对，但不过这样成本太高了。能保证计算机中心能两两之间有通路即可吗？
是的，以下来自wiki的图，顶点表示计算机中心，之间连续用边表示，其中边的权值就是费用。
从一个图中抽掉那些高昂的费用但有不破坏图的连通性。
由于我们只需要保证连通和最低费用就可以了。任意两个顶点之间只需要一条边连接就足够了。
那么，按照上述删除连通无向图中的边的最终结构会形成一棵树（如下图黑色的边形成的树）。
这颗树就是最小生成树。
在这里插入图片描述

详细部分请向下看
最小生成树的两种算法都是基于贪心的策略，即寻找局部最优解。
Kruskal算法是一种贪心算法，它从边的角度出发，用于带权无向图在寻找最小生成树，它不需要建图，只需要用一个高效数据结构并查集就搞定了。
Prim算法留到下一篇再谈。

2. 最小生成树的性质

什么图具有最小生成树：
- 满足无向,带权,连通这些特征的图具有最小生成树。
最小生成树的定义：
- 连通图中所有的顶点并且边权重之和最小的树结构
相关性质：
- 生成树的边数为 $n - 1$ , 树结构的基本性质，注:n是顶点的个数。
- 不会成环。
最小生成树不唯一：
最小生成树的权值要求最小，但边的组织可能不同，因此结构并不唯一。存在多种最小生成树结构（但这些树的最小权重和是相同的）。

3. Kruskal 算法详解

3.1 Kruskal 的核心思想
- 每次选择最小的边，将边添加进树结构里。期间可能存在成环情况（借助并查集判环），直到添加了n-1条边结束。
3.2 算法流程
1. 若给了图，那么遍历图中所有的边将它们排好序；或者，收集好边的信息（两个端点，权重）排序。
2. 按边权值升序排序。
3. 使用并查集判断边是否形成环。（具体看代码）
4. 逐步加入边，直到添加到n-1条边为止。
3.3 为什么正确性
基于贪心的策略，每次选择权值最小的边且这条边不会成环或破坏连通性。局部最优 == 全局最优。严格证明不必纠结。

4. Kruskal 算法的实现

4.1 数据结构选择
- 使用并查集（Union-Find）O(1)的时间进行合并，高效地检测环。
- 前面可以通过排序数组，用样可以选择优先级队列或者广泛的堆结构。
4.2 实现细节
- 对边信息的处理
- 并查集实现:路径压缩，按秩排序（我这里代码并未实现）
4.3 Java代码实现
Kruskal模板题

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main{//最大数据量public static int MAXN = 5001;public static int MAXM = 200001;//并查集模板数组public static int[] father = new int[MAXN];//边信息的处理public static int[][] edges = new int[MAXM][3];public static int n, m;//初始化并查集public static void build(int n){for(int i=1;i<=n;i++){father[i] = i;}}//向上找标记节点，并完成路径压缩public static int find(int i){if(i != father[i]){father[i] = find(father[i]);}return father[i];}//x，y不属于同一个集合就合并返回true//否则返回false.public static boolean union(int x,int y){int fx = find(x);int fy = find(y);if(fx == fy){return false;}else{father[fx] = fy;return true;}}public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while(in.nextToken() != StreamTokenizer.TT_EOF){n = (int)in.nval;in.nextToken();m = (int)in.nval;build(n);for(int i=1;i<=m;i++){in.nextToken();edges[i][0] = (int)in.nval;in.nextToken();edges[i][1] = (int)in.nval;in.nextToken();edges[i][2] = (int)in.nval;}//Kruskal依赖边权值的有序性//比较器快排一下。Arrays.sort(edges,1,m+1,(a,b) -> a[2] - b[2]);int ans = 0;int count = 0;//遍历所有边for(int[] edge : edges){//边的两个顶点不在并查集里， 合并两个并查集//将边添加进最小生成树中。if(union(edge[0], edge[1])){count++;ans += edge[2];}}out.println(count == n-1 ? ans : "orz");}out.flush();out.close();br.close();}
}