定义#

最小生成树是指在一张无向图中，选取一些边，使其满足以下条件：

选择的边能够使图中的每一个节点直接或间接相连
在满足条件 1 的前提下，使得所有边的和尽可能小．（即获得连通所有点的最小代价）

[!node]- 题目：P3366 最小生成树
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz．
输入格式#
第一行包含两个整数 $N,M$ ，表示该图共有 $N$ 个结点和 $M$ 条无向边．
接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$ ，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$ ．
输出格式#
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和．如果该图不连通则输出 orz．
数据范围#
对于 $100\%$ 的数据： $1\le N\le 5000$ ， $1\le M\le 2\times 10^5$ ， $1\le Z_i \le 10^4$ ．

kruskal 算法#

kruskal 算法的本质是贪心，主要分为以下几步

先将所有边按权值从小到大排序．
依次选择权值最小的边，如果这条边连接的两个端点不在同一个连通块（即不形成环），就将这条边加入生成树．
重复上述过程，直到选出 n-1 条边（n 为节点数），或者所有边都被处理完．
如果仍旧有点没有被连通，那么原图就不是连通图

判断两个边是否连通，常使用并查集．

时间复杂度： $O(m)$

标程——kruskal#

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 100;
const int M = 2e5 + 100;
int n, m;

int f[N];

// 定义一条边
struct Edge
{
	// u表示边的起点
	// v表示边的终点
	// w表示边的权值
	int u, v, w;
	friend bool operator<(Edge a, Edge b)
	{
		return a.w < b.w;
	}
} e[M];

// 并查集模板
class DSU
{
public:
	// 初始化并查集
	void build(int size)
	{
		for (int i = 1; i <= size; i++)
		{
			f[i] = i;
		}
	}
	// 找到节点t的最顶端的父节点
	int find(int t)
	{
		if (f[t] != t)
			f[t] = find(f[t]);
		return f[t];
	}
	// 将节点a和节点b所在集合合并
	void merge(int a, int b)
	{
		int x = find(a), y = find(b);
		if (x != y)
			f[x] = y;
	}
	// 查询a和b是否处于同一集合
	bool query(int a, int b)
	{
		return find(a) == find(b);
	}
} dsu;

void kruskal()
{
	// 进行排序
	sort(e + 1, e + m + 1);
	int ans = 0;
	// 依次选取每一条边，尝试添加
	for (int i = 1; i <= m; i++)
	{
		int u = e[i].u, v = e[i].v;
		if (!dsu.query(u, v))
		{
			ans += e[i].w;
			dsu.merge(u, v);
		}
	}
	// 判断是否连通
	for (int i = 1; i <= n; i++)
	{
		if (!dsu.query(1, i))
		{
			cout << "orz" << endl;
			return;
		}
	}
	cout << ans << endl;
	return;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	dsu.build(n);
	kruskal();
}

cpp

prim 算法#

Prim 算法也是一种贪心．

核心思想：

从任意一个点出发，每次选择一条连接已选点集和未选点集、权值最小的边，将新点加入生成树．
重复 n-1 次，直到所有点都被包含．

常用优先队列（堆）优化，时间复杂度 $O(m\log n)$ ．

适合稠密图，代码实现类似 Dijkstra，但 Prim 关注的是“连通所有点的最小代价”，不是最短路．

标程——prim#

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 100;
const int M = 2e5 + 100;
int n, m;

struct Edge
{
	int to, w;
	friend bool operator<(Edge a, Edge b)
	{
		return a.w > b.w;
	}
};

vector<Edge> e[N];
bool mark[N];

void prim()
{
	int ans = 0;
	priority_queue<Edge> q;
	q.push({1, 0});
	while (!q.empty())
	{
		int v = q.top().to, w = q.top().w;
		q.pop();
		if (mark[v])
			continue;
		mark[v] = true;
		ans += w;
		for (int i = 0; i < e[v].size(); i++)
		{
			q.push(e[v][i]);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!mark[i])
		{
			cout << "orz";
			return;
		}
	}
	cout << ans;
	return;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	prim();
}

cpp