# 最小生成树 Minimum Spanning Tree
加权无向图的最小生成树(Minimum Spanning Tree,简称 MST)是一棵生成树,其权(所有边的权值之和)不会大于其它任何生成树的权。
一个带权连通图 G(假定每条边上的权值均大于零)可能有多棵生成树.
每棵生成树中所有边上的权值之和可能不同。
其中边上的权值之和最小的生成树称为图的最小生成树。
MST 算法有很多,但其中最知名的是 Prim 算法和 Kruskal 算法
# Prim 算法
# 基本思路
从任何一个顶点开始作一棵单顶点 MST,再为之增加 V-1 条边,每次增加的边都是将 MST 上的一个顶点和尚未在此 MST 上的一个顶点相连接的最小边。
假设 G=(V,E) 是一个具有 n 个顶点的带权连通图,T=(U,TE) 是 G 的最小生成树,其中 U 是 T 的顶点集,TE 是 T 的边集,则由 G 构造从起始点 v 出发的最小生成树 T 的步骤如下:
- 初始化 U={v}。以 v 到其他顶点的所有边为候选边。
- 重复以下步骤 n-1 次,使得其他 n-1 个顶点被加入到 U 中:
- 从候选边中挑选权值最小的边加入 TE(所有候选边一定是连接两个顶点集 U 和 V-U 的边),设该边在 V-U 中的顶点是 k,将顶点 k 加入 U 中。
- 考察当前 V-U 中的所有顶点 j,修改候选边:若 (k,j) 的权值小于原来和顶点 j 关联的候选边,则用 (k,j) 取代后者作为候选边。
寻找最小边在这里使用小根堆
# 基于堆的 Prim 算法代码
struct Edge { | |
int from, to, cost; | |
Edge(int u, int v, int w):from(u), to(v), cost(w) {} | |
}; | |
struct HeapNode { | |
int d, u; //d 表示点 u 到 MST 的距离 | |
bool operator< (const HeapNode& rhs) const { | |
return d > rhs.d; // 小根堆 | |
} | |
}; | |
vector<Edge> edges; //edges 存所有边 | |
vector<int> G[MAXN]; // G [i] 是顶点 i 发出的所有边 | |
bool done[MAXN]; //i 是否已经加入了 MST | |
int d[MAXN]; // 每个点到 MST 的最小距离 | |
int Prim() { | |
priority_queue<HeapNode> Q; | |
int ans = 0; // 总权值 | |
for (int i = 0; i < V; ++i) d[i] = INF; // V 是图的节点数 | |
d[0] = 0; // 从点 0 开始 | |
memset(done, 0, sizeof(done)); | |
Q.push((HeapNode){0, 0}); | |
while (!Q.empty()) { | |
HeapNode x = Q.top(); Q.pop; | |
int u = x.u; //u 为队头元素的序号 | |
if (done[u]) continue; // 已经在 MST 中就跳过 | |
ans += x.d; // 加上出队的队头元素到 MST 的距离 | |
done[u] = true; | |
for (int i = 0; i < G[u].size; ++i) { // 更新最小生成树的权值 | |
Edge& e = edges[G[u][i]]; // 顶点 to 能修改最小距离 | |
if (d[e.to] > e.cost) { | |
d[e.to] = e.cost; | |
Q.push((HeapNode){d[e.to], e.to}); | |
} | |
} | |
} | |
return ans; | |
} |
# 注意
本段代码用邻接表来存图,输入可以使用
for (int i = 0; i < E; ++i) { // E 是边数 | |
int u, v, cost; | |
cin >> u >> v >> cost; // 输入边的起点、终点和权值 | |
G[u].push_back(i); // 存储边的索引 | |
edges.push_back(Edge(u, v, cost)); | |
G[v].push_back(i); // 存储边的索引 | |
edges.push_back(Edge(v, u, cost)); | |
} |
# 分析
Prim 时间复杂度为。在稀疏图的情况下,E 的数量通常远小于,因此可以将时间复杂度近似为。而在稠密图的情况下,E 的数量接近,时间复杂度会接近。
# Kruskal 算法
# 基本思路
以边的长度(从小到大)为顺序来处理,若一条边与前面加入到 MST 中的边未形成环,则将这样的边加入到 MST 中,增加了 V-1 条边后停止。也就是说开始是一个森林,每个顶点就是一棵独立的树,然后逐渐把这些树合并(通过一条最小边),最后形成的一棵树就是 MST。
假设 G=(V,E) 是一个具有 n 个顶点的带权连通图,T=(U,TE) 是 G 的最小生成树,则构造最小生成树的步骤如下:
- 置 U 的初值等于 V(即包含有 G 中的全部顶点),TE 的初值为空集(即图 T 中每一个顶点都构成一个分量)。
- 将图 G 中的边按权值从小到大的顺序依次选取:若选取的边未使生成树 T 形成回路,则加入 TE;否则舍弃,直到 TE 中包含 n-1 条边为止。
如果把一棵树看成一个集合,那么对于新加入的边,要判断它的两个顶点是否已经在同一个集合了?是的话就跳过,处理下一条边;不是的话就把这条边加入到 MST,同时把该边两顶点所处的两个集合合并。这个实际就是不相交集合(Disjoint Set)的并查 (Union-Find) 操作。
# Kruskal 算法代码
struct edge { | |
int u, v, cost; | |
}; | |
bool cmp(const edge& e1, const edge& e2) { | |
return e1.cost < e2.cost; | |
} | |
edge es[MAX_E]; // 存储边的信息 | |
int par[MAX_V]; // 存储父节点 | |
// 初始化并查集 | |
void init_union_find(int V) { | |
for (int i = 0; i < V; ++i) { | |
par[i] = i; // 初始时每个节点的父节点是自身 | |
} | |
} | |
// 查找根节点 | |
int find(int x) { | |
if (par[x] == x) { | |
return x; // 根节点的父节点是自身 | |
} else { | |
return par[x] = find(par[x]); // 路径压缩,将 x 的父节点设为根节点,加速后续查找 | |
} | |
} | |
// 合并集合 | |
void unite(int x, int y) { | |
x = find(x); // 查找 x 的根节点 | |
y = find(y); // 查找 y 的根节点 | |
if (x != y) { | |
par[x] = y; // 将 x 的根节点设为 y,合并两个集合 | |
} | |
} | |
// 判断两个节点是否属于同一个集合 | |
bool same(int x, int y) { | |
return find(x) == find(y); // 若两个节点的根节点相同,则属于同一个集合 | |
} | |
int Kruskal(int V, int E) { | |
sort(es, es + E, cmp); // 按权值从小到大排序 | |
init_union_find(V); // 并查集初始化 | |
int res = 0; | |
for (int i = 0; i < E; ++i) { | |
edge e = es[i]; | |
if (!same(e.u, e.v)) { //u 和 v 不属于一个集合 | |
unite(e.u, e.v); // 合并 u 和 v 集合的元素 | |
res += e.cost; | |
} | |
} | |
return res; | |
} |
# 分析
Kruskal 算法的时间复杂度为。在稀疏图的情况下,E 的数量通常远小于,因此可以将时间复杂度近似为。而在稠密图的情况下,E 的数量接近,时间复杂度会接近。