最小生成树 & 严格次小生成树

最小生成树

作甚最小生成树？

有一类题目：给定一张图，可以删除若干条边，在不改变连通性（一般是全联通）的情况下，权值和最小的方案是什么？没错，这就是最小生成树题目（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:

1. #include <iostream>
2. #include <vector>
3. #include <climits>
4. using namespace std;
6. const int MAXN = 5005;
7. const int INF = INT_MAX;
9. int n, m; // 顶点数和边数
10. int graph[MAXN][MAXN]; // 邻接矩阵存储图
11. int dist[MAXN]; // 存储顶点到MST的最小距离
12. bool visited[MAXN]; // 标记顶点是否已在MST中
14. void prim() {
15.     // 初始化距离数组
16.     fill(dist, dist + n + 1, INF);
17.     fill(visited, visited + n + 1, false);
18.    
19.     dist[1] = 0; // 从顶点1开始
20.    
21.     int totalWeight = 0; // 最小生成树的总权重
22.     int selected = 0; // 已选顶点数
23.    
24.     for (int i = 1; i <= n; ++i) {
25.         int u = -1;
26.         // 找到未访问的距离最小的顶点
27.         for (int j = 1; j <= n; ++j) {
28.             if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
29.                 u = j;
30.             }
31.         }
32.         
33.         // 如果没有找到可达的顶点，说明图不连通
34.         if (dist[u] == INF) {
35.             cout << "orz" << endl;
36.             return;
37.         }
38.         
39.         visited[u] = true;
40.         totalWeight += dist[u];
41.         selected++;
42.         
43.         // 更新邻接顶点的距离
44.         for (int v = 1; v <= n; ++v) {
45.             if (!visited[v] && graph[u][v] < dist[v]) {
46.                 dist[v] = graph[u][v];
47.             }
48.         }
49.     }
50.    
51.     if (selected == n) {
52.         cout << totalWeight << endl;
53.     } else {
54.         cout << "-1" << endl;  //无法构成MST。
55.     }
56. }
58. int main() {
59.     cin >> n >> m;
60.    
61.     // 初始化邻接矩阵
62.     for (int i = 1; i <= n; ++i) {
63.         for (int j = 1; j <= n; ++j) {
64.             graph[i][j] = INF;
65.         }
66.     }
67.    
68.     // 读入边
69.     for (int i = 0; i < m; ++i) {
70.         int u, v, w;
71.         cin >> u >> v >> w;
72.         if (w < graph[u][v]) { // 处理重边，保留权重最小的
73.             graph[u][v] = graph[v][u] = w;
74.         }
75.     }
76.    
77.     prim();
78.    
79.     return 0;
80. }

复制代码

时间复杂度 \(O(m \log m)\),空间复杂度 \(O(n)\) 。
Kruskal 算法

再次观察题目，有没有什么由代价的信息呢？我们发现，添加一条边的过程实际上和并查集归并的过程如出一辙！欸，我们又找到了思路，没错，可以用并查集来寻找最小生成树。过程如下：

• 初始化并查集，如今有 \(n\) 个连通块和 \(0\) 条边。
  
• 如今排序所有边，按权值来排。
  
• 遍历边集数组，归并对于第 \(i\) 条边的起点和终点，归并乐成的话就计入答案，直到连通块个数为 \(1\)。
  那么为什么这个方案可行呢？我们恣意画张图就知道了：
  

• 首先，如果两个节点不属于一个集合，那么会归并两个联通块，连通块个数减少 \(1\) 个。
  
• 如果两个节点本来就属于一个节点，意味着再加入一条边就会形成环，故不会发生这样的情况，归并失败。
  
• 末了，由于我们的边集数组是一个有序（递增）的数组，因此也不存在会浪费掉恣意一条最小生成树上的边，结果是最优的。
  

Code:

[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[rootU] = rootV;            total += edges.w;            selected++;            if (selected == n - 1) break; // 已选够n-1条边        }    }    // 输出结果    if (selected == n - 1) cout