Kruskal 最小生成树

最小生成树

一个图的子图中边权和最小的树称为最小生成树。

所以，如果一张子图是最小生成树，那么一定满足下列条件：

这张子图包括原图的所有顶点；
这张子图是树；
这张子图是满足前两个条件的子图中边权和最小的。

Kruskal 算法

前言和优点介绍

Kruskal 算法是一种用来寻找最小生成树的算法，由 Joseph Kruskal 在 1956 年发表。用来解决同样问题的还有 Prim 算法和 Boruvka 算法等。三种算法都是贪心算法的应用。Kruskal 算法在图中存在相同权值的边时也仍然有效。

kruskal 算法是竞赛中最常用的最小生成树算法（相较于 prim 算法而言），原因有下：

kruskal 在一个 $n$ 个顶点 $m$ 条边的联通图中时间复杂度为 $m\log m$ ，可接受；
kruskal 算法可以借助堆和并查集来实现，前者即 stl 当中的 priority_queue，后者并查集写起来十分简单，所以难度不大。

思路

算法的具体步骤为：

我们先假设最终的要生成的最小生成树为子图 $G'$ ，原图称为 $G$ 。

将图 $G$ 中所有边依次加入集合中。初始假定图 $G'$ 中所有点相互独立。
取出集合中边权最小的边，判断边的两断电在 $G'$ 中是否联通。
如果联通说明两个点已经有其它边将两点联通了，那么跳过这条边，如果不连通，说明这条边属于最小生成树，将这条边加入 $G'$ 之中。
重复 $2$ ， $3$ 操作直到集合为空。此时被选择的边构成最小生成树。

★ 那么，问题来了，如何快速查找最短边呢？如何判断两个点在子图中是否连通呢？

可以将所有边放入优先队列（按权值从小到大排序），这样一来就可以实现 $\log n$ 查询最小边了。
而在 kruskal 中，我们不需要动态最小值，所以 sort 也可以进行排序。

判断联通可以使用并查集，并查集每次合并和查询的时间复杂度为 $\operatorname{Ackermann}^{-1}(n)$ ，即阿克曼函数的反函数的时间复杂度，可以忽略为常数。

正确性证明

Kruskal 算法的本质，就是开始时将所有点看为独立的树，在整个过程中不停的找到最短的边，其两端连接的树没有被合并，就将其合并在一起，我们要证明的，是对于整张图 $G$ ，对于点集 $A$ 和 $B$ ，满足 $A\cap B=\empty$ ，假设 $T_A$ 为 $A$ 的最小生成树， $T_B$ 为 $B$ 的最小生成树，且 $\exist e(u,v)\in G$ ， $u\in A$ ， $v\in B$ ，选择所有连接 $A$ 和 $B$ 之间的边 $e$ 中最小的，将 $T_A$ 和 $T_B$ 两棵生成树合并，需要证明的是，这样的选择得到的新生成树 $T_{A\cup B}=T_A\cup T_B\cup {e}$ 对于点集 $A\cup B$ 生成树中是最小的一个。

从结果论的角度考虑，对于生成树 $T_{A\cup B}$ ，一定可以拆成 $T_A$ 、 $T_B$ 和一条边 ${e}$ 的形式，那么若 $T_A$ 和 $T_B$ 确定，很显然 $e$ 应当是所有连接 $A$ 和 $B$ 中点的边中最小的那条。

适用范围

因为 kruskal 算法时间复杂度为 $m\log m$ ，相比于时间复杂度为 $m \log n$ 的 Prim 算法，在稀疏图中会效果更好，但由于 $\log_2 n$ 和 $\log_2 m$ 的差距非常小，可以忽略。

对于几乎所有的题目，通常两种算法都可过。

kruskal 算法代码

// sort 版
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+4,M=2e5+4;
int n,m;
int res,ct;
int fa[N];
int find(int id) {
	return (fa[id]==id)?id:(fa[id]=find(fa[id]));
}
void merge(int a,int b) {
	fa[find(a)]=fa[find(b)];
}
vector<pair<int,int>> g[M];
vector<pair<int,pair<int,int>>> q;
void read() {
	cin>>n>>m;
	for(int i=1,st,ed,wt;i<=m;++i) {
		cin>>st>>ed>>wt;
		g[st].push_back({ed,wt});
	}
}
void kruskal() {
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1;i<=n;++i)
		for(auto c:g[i])
			q.push_back(make_pair(c.second,make_pair(i,c.first)));
	sort(q.begin(),q.end());
	for(int i=0;i<q.size();++i) {
		auto c=q[i];
		int st=c.second.first;
		int ed=c.second.second;
		int wt=c.first;
		if(find(st)==find(ed)) continue;
		res+=wt,ct++;
		merge(st,ed);
	}
	if(ct!=n-1) cout<<"orz\n";
	else cout<<res<<'\n';
}
int main() {
    read();
    kruskal();
    return 0;
}