最小生成树 & 严格次小生成树
最小生成树何为最小生成树？
有一类问题：给定一张图，可以删除若干条边，在不改变连通性（一般是全联通）的情况下，权值和最小的方案是什么？没错，这就是最小生成树问题（MST问题）。那么基本性质其实连聪明的小学生都能看出来，应当使得最后留下 \(n-1\) 条边且没有环路得到情况下才有可能构成生成树，这便是Kruskal的基本实现原则，这个后面会讲。
最小生成树的Prim算法
其实Prim本身还是比较好理解的，跟Dijstra没什么两样，方法如下：
[*]随便选一个结点出发，一般选定节点编号为 \(1\)，标记为 \(now\)，但请注意：只有在图全联通的情况下才能这么做。
[*]向当前节点能够走到的所有节点进行搜索，如果当前 dis 值小于对于当前 \(now\) 的更新后的节点最大值，那就更新 dis，并记录下此节点。
[*]当遍历完 \(now\) 所有能去到的节点之后，留下的就是对于更新后的，对于 \(now\) 能走到的节点权值最小值的编号，将其列为访问过，并计入到最小生成树中。
[*]访问这个被记入访问了的节点，并重复 \(2\) 到 \(3\) 步直到推出结果。
为什么这个算法可行呢？
[*]首先我们确保了每次选中的变得权值是最小的。
[*]由于每个节点至多且一定会被选中 \(1\) 次，所以就会被选中 \(n-1\) 条边（最后一次更新没有选边）。
和上述我们面熟的的最小生成树的定义一样一样的，恭喜你，学会了Prim算法。对于其时间复杂度，是 \(O(n^2)\) （\(n\) 为节点数） ，空间复杂度是 \(O(n)\) ，非常稳定，（唯一的缺点就是慢）。
Code:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int MAXN = 5005;
const int INF = INT_MAX;
int n, m; // 顶点数和边数
int graph; // 邻接矩阵存储图
int dist; // 存储顶点到MST的最小距离
bool visited; // 标记顶点是否已在MST中
void prim() {
// 初始化距离数组
fill(dist, dist + n + 1, INF);
fill(visited, visited + n + 1, false);
dist = 0; // 从顶点1开始
int totalWeight = 0; // 最小生成树的总权重
int selected = 0; // 已选顶点数
for (int i = 1; i <= n; ++i) {
int u = -1;
// 找到未访问的距离最小的顶点
for (int j = 1; j <= n; ++j) {
if (!visited && (u == -1 || dist < dist)) {
u = j;
}
}
// 如果没有找到可达的顶点，说明图不连通
if (dist == INF) {
cout << "orz" << endl;
return;
}
visited = true;
totalWeight += dist;
selected++;
// 更新邻接顶点的距离
for (int v = 1; v <= n; ++v) {
if (!visited && graph < dist) {
dist = graph;
}
}
}
if (selected == n) {
cout << totalWeight << endl;
} else {
cout << "-1" << endl;//无法构成MST。
}
}
int main() {
cin >> n >> m;
// 初始化邻接矩阵
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
graph = INF;
}
}
// 读入边
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
if (w < graph) { // 处理重边，保留权重最小的
graph = graph = w;
}
}
prim();
return 0;
}时间复杂度 \(O(m \log m)\),空间复杂度 \(O(n)\) 。
Kruskal 算法
再次观察题目，有没有什么由价值的信息呢？我们发现，添加一条边的过程实际上和并查集合并的过程如出一辙！欸，我们又找到了思路，没错，可以用并查集来寻找最小生成树。过程如下：
[*]初始化并查集，现在有 \(n\) 个连通块和 \(0\) 条边。
[*]现在排序所有边，按权值来排。
[*]遍历边集数组，合并对于第 \(i\) 条边的起点和终点，合并成功的话就计入答案，直到连通块个数为 \(1\)。
那么为什么这个方案可行呢？我们随便画张图就知道了：
[*]首先，如果两个节点不属于一个集合，那么会合并两个联通块，连通块个数减少 \(1\) 个。
[*]如果两个节点本来就属于一个节点，意味着再加入一条边就会形成环，故不会发生这样的情况，合并失败。
[*]最后，因为我们的边集数组是一个有序（递增）的数组，因此也不存在会浪费掉任意一条最小生成树上的边，结果是最优的。
Code:
#include #include using namespace std;const int MAXM = 2e5 + 5; // 边数上限const int MAXN = 5005; // 点数上限struct Edge { int u, v, w; bool operator> n >> m; // 初始化并查集 for (int i = 1; i > edges.u >> edges.v >> edges.w; } // 按边权排序 sort(edges, edges + m); int selected = 0; // 已选边数 long long total = 0; // 总权值 // 克鲁斯卡尔主过程 for (int i = 0; i < m; i++) { int u = edges.u, v = edges.v; int rootU = find(u), rootV = find(v); if (rootU != rootV) { // 不连通则合并 fa = rootV; total += edges.w; selected++; if (selected == n - 1) break; // 已选够n-1条边 } } // 输出结果 if (selected == n - 1) cout
页:
[1]