最小生成树 MST：Kruskal 与 Prim

前言

一个有 $n$ 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 $n$ 个结点，并且有保持图连通的最少的边，称作最小生成树 (Minimum Spanning Tree, MST) 。

最小生成树可以用 Kruskal（克鲁斯卡尔）算法或 Prim（普里姆）算法求出。

Kruskal 算法

假设 $G=(V,E)$ 是一个含有 $n$ 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：

先构造一个只含 $n$ 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 $n$ 棵树的一个森林。
之后，从网的边集 $E$ 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；
反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。
依次类推，直至森林中只有一棵树，也即子图中含有 $n-1$ 条边为止。

实现时按边权从小到大排序逐条取边，“分属不同的树”用并查集判断：两端点不在同一集合就合并、累加权值。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 5005, M = 200005;		//n、m 的上限，按题目范围调整

int n, m, fa[N];

struct Edge
{
	int u, v, w;
	bool operator<(const Edge &t) const { return w < t.w; }
} e[M];

int find(int x)						//并查集找根
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

long long kruskal()
{
	for (int i = 1; i <= n; ++i)
		fa[i] = i;
	sort(e + 1, e + m + 1);			//按边权从小到大排序
	long long res = 0;
	int cnt = 0;
	for (int i = 1; i <= m; ++i)
	{
		int fu = find(e[i].u), fv = find(e[i].v);
		if (fu != fv)				//两端点分属不同的树，合并这两棵树
		{
			fa[fu] = fv;
			res += e[i].w;
			++cnt;
		}
	}
	if (cnt < n - 1) return -1;		//取不满 n-1 条边，原图不连通
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	printf("%lld\n", kruskal());
	return 0;
}

排序是主要开销，复杂度 $O(m\log m)$ 。

Prim 算法

假设 $G=(V,E)$ 是一个含有 $n$ 个顶点的连通网，则按照 Prim 算法构造最小生成树的过程为：

首先，定义 Vnew={x} ，其中 $x$ 为集合 $V$ 中的任一节点（起始点）；定义 Enew={} 。
接着，在集合 $E$ 中选取权值最小的边 $<u,v>$ ，其中 $u$ 为集合 $V_{new}$ 中的元素，而 $v$ 不在 $V_{new}$ 集合当中，且 $v\in V$ （如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；将 $v$ 加入集合 $V_{new}$ 中，将 $<u, v>$ 边加入集合 $E_{new}$ 中。
重复以上步骤，直到 $V_{new}=V$ 。
最后，使用集合 $V_{new}$ 和 $E_{new}$ 来描述所得到的最小生成树。

实现时给每个还没进树的点记一条连向树的最短边，全部丢进小根堆，每次取堆顶对应的点加入 $V_{new}$ ，再用它更新相邻的点。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;			//(边权，点)

const int N = 5005, M = 200005;		//n、m 的上限，按题目范围调整，点编号 1~n

int n, m, head[N], tot;
int to[2 * M], nxt[2 * M], w[2 * M];
int dis[N];							//每个点连向已生成部分的最短边
bool vis[N];

void add(int u, int v, int c)		//邻接表加边
{
	to[++tot] = v;
	w[tot] = c;
	nxt[tot] = head[u];
	head[u] = tot;
}

long long prim()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> q;	//小根堆
	q.push(make_pair(0, 1));
	long long res = 0;
	int cnt = 0;
	while (!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;		//堆里存的是旧边，取过的点跳过
		vis[u] = true;
		res += dis[u];
		++cnt;
		for (int i = head[u]; i; i = nxt[i])
		{
			int v = to[i];
			if (!vis[v] && w[i] < dis[v])
			{
				dis[v] = w[i];		//v 连向已生成部分的最短边变短了
				q.push(make_pair(dis[v], v));
			}
		}
	}
	if (cnt < n) return -1;			//扩不满 n 个点，原图不连通
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
	{
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		add(u, v, c);
		add(v, u, c);
	}
	printf("%lld\n", prim());
	return 0;
}

每条边进出堆一次，堆优化后的复杂度是 $O(m\log n)$ 。稀疏图（ $m$ 与 $n$ 同阶）用 Kruskal 就够了，稠密图（ $m$ 接近 $n^2$ ）用 Prim。

参考资料：

部分资料来源于百度百科「最小生成树」词条

前言

Kruskal 算法

Prim 算法

继续读