最小生成树
简介 #
无向图
$G$ 的生成树满足以下性质：
图 $b$ 和图 $c$ 皆为图 $a$ 的生成树.
最小生成树，即边权和最小的生成树.对于 $n$ 个节点的无向图，最小生成树一定有 $n-1$ 条边.
Kruskal 算法 #
Kruskal 是一种贪心算法.
- 将 $m$ 条边按照边权升序排序；
- 从小到大枚举边：
- 若此边的两个顶点未连通，则在树中加入此边，并连通两个顶点.
- 若此边的两个顶点已连通，直接跳到下一条边.
重复直到树中共加入 $n-1$ 条边.
使用
并查集 判断和维护两个顶点是否连通.
时间复杂度为 $O(m\log{m})$，适用于稀疏图.
const int N = 1e6;
int n, m, fa[N];
struct edge { int x, y, len; } g[N];
bool cmp(edge x, edge y) {
return x.len < y.len;
}
int find(int x) {
return !fa[x] ? x : fa[x] = find(fa[x]);
}
int kruskal() {
sort(g + 1, g + m + 1, cmp);
int tot = 0, sum = 0;
for(int i = 1; i <= m; i ++) {
if(tot == n - 1) break;
int rx = find(g[i].x);
int ry = find(g[i].y);
if(rx != ry) {
tot ++, fa[rx] = ry, sum += g[i].len;
}
}
return tot == n - 1 ? sum : -1; //如果存在最小生成树，则返回边权和，否则返回 -1
}Prim 算法 #
$dis[u]$ 表示节点 $u$ 到树的最短距离.
- 建立一棵只有 $1$ 号节点的树，$dis[1]=0$；
- 选择离树最近（$dis$ 最小）的节点加入树，对该点的所有临边进行
松弛操作.重复执行直到加入 $n-1$ 条边.
时间复杂度为 $O(n^2)$，适用于稠密图.
int prim() {
int sum = 0;
memset(avl, true, sizeof avl);
memset(dis, 0x7f, sizeof dis);
dis[1] = 0;
for(int i = 2; i <= n; i ++) {
int minn = INF, minp = 0;
for(int j = 2; j <= n; j ++)
if(avl[j] && dis[j] < minn)
minn = dis[j], minp = j;
if(!minp) return -1;
avl[minp] = false, sum += minn;
for(int j = 1; j <= n; j ++)
if(avl[j] && dis[j] > g[minp][j])
dis[j] = g[minp][j];
}
return sum;
}