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

技术分享 9个月前 (05-01) 0 999+

最小生成树

何为最小生成树？

有一类问题：给定一张图，可以删除若干条边，在不改变连通性（一般是全联通）的情况下，权值和最小的方案是什么？没错，这就是最小生成树问题（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[MAXN][MAXN]; // 邻接矩阵存储图 int dist[MAXN]; // 存储顶点到MST的最小距离 bool visited[MAXN]; // 标记顶点是否已在MST中  void prim() {     // 初始化距离数组     fill(dist, dist + n + 1, INF);     fill(visited, visited + n + 1, false);          dist[1] = 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[j] && (u == -1 || dist[j] < dist[u])) {                 u = j;             }         }                  // 如果没有找到可达的顶点，说明图不连通         if (dist[u] == INF) {             cout << "orz" << endl;             return;         }                  visited[u] = true;         totalWeight += dist[u];         selected++;                  // 更新邻接顶点的距离         for (int v = 1; v <= n; ++v) {             if (!visited[v] && graph[u][v] < dist[v]) {                 dist[v] = graph[u][v];             }         }     }          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[i][j] = INF;         }     }          // 读入边     for (int i = 0; i < m; ++i) {         int u, v, w;         cin >> u >> v >> w;         if (w < graph[u][v]) { // 处理重边，保留权重最小的             graph[u][v] = graph[v][u] = w;         }     }          prim();          return 0; }

堆优化Prim算法

既然Prim那么慢，有没有什么好方法来优化掉这个致命的问题呢？当然有，我们可以使用优先队列来优化掉这个Prim算法。
思考：既然每次选点我们都只选最小的那个节点，而并不关心别的节点怎么了（~~看来图论的世界也只容得下第一名啊~~），欸，刚好和我们优先队列一拍即合，没错，他们两个需要维护的东西完全一致，那么就用堆来优化Prim好了：

首先我们创建一个 priority_queue，且是小根堆。
把 (now) 压入队列。
弹出队首，叫做 (cur) 。
检查 (cur) 是不是已经被访问过，如果是，就跳过。
遍历 (cur) 能抵达的所有节点，执行上述根性操作并push。
6.重复 (2) ~ (5) 步，直到我们求出MST。
其实堆优化Prim不是一种模板，是一种思想，就是要学会怎么找到题目中可以优化掉的没有用的信息，看有没有合适的优化方法，这种思想就是这么多高级算法的最终的最终的源头。

Code

#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std;  const int MAXN = 5005; const int INF = INT_MAX;  typedef pair<int, int> pii; // (weight, vertex)  int n, m; vector<pii> adj[MAXN]; // 邻接表存储图 int dist[MAXN]; // 存储顶点到MST的最小距离 bool visited[MAXN]; // 标记顶点是否已在MST中  void prim_heap() {     fill(dist, dist + n + 1, INF);     fill(visited, visited + n + 1, false);          priority_queue<pii, vector<pii>, greater<pii>> pq; // 最小堆          dist[1] = 0;     pq.push({0, 1});          int totalWeight = 0;     int selected = 0;          while (!pq.empty() && selected < n) {         int u = pq.top().second;         int d = pq.top().first;         pq.pop();                  if (visited[u]) continue;         visited[u] = true;         totalWeight += d;         selected++;                  for (auto &edge : adj[u]) {             int v = edge.second;             int w = edge.first;             if (!visited[v] && w < dist[v]) {                 dist[v] = w;                 pq.push({dist[v], v});             }         }     }          if (selected == n) {         cout << totalWeight << endl;     } else {         cout << "-1" << endl;     } }  int main() {     cin >> n >> m;          // 读入边     for (int i = 0; i < m; ++i) {         int u, v, w;         cin >> u >> v >> w;         adj[u].push_back({w, v});         adj[v].push_back({w, u});     }          prim_heap();          return 0; }

时间复杂度 (O(m log m)),空间复杂度 (O(n)) 。

Kruskal 算法

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

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

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

Code:

#include <iostream> #include <algorithm> using namespace std;  const int MAXM = 2e5 + 5; // 边数上限 const int MAXN = 5005;    // 点数上限  struct Edge {     int u, v, w;     bool operator<(const Edge &other) const {         return w < other.w; // 按边权升序排序     } } edges[MAXM];  int fa[MAXN]; // 并查集父节点数组  // 并查集查找根节点（路径压缩） int find(int x) {     return fa[x] == x ? x : fa[x] = find(fa[x]); }  int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);      int n, m;     cin >> n >> m;      // 初始化并查集     for (int i = 1; i <= n; i++) fa[i] = i;      // 读入边     for (int i = 0; i < m; i++) {         cin >> edges[i].u >> edges[i].v >> edges[i].w;     }      // 按边权排序     sort(edges, edges + m);      int selected = 0; // 已选边数     long long total = 0; // 总权值      // 克鲁斯卡尔主过程     for (int i = 0; i < m; i++) {         int u = edges[i].u, v = edges[i].v;         int rootU = find(u), rootV = find(v);         if (rootU != rootV) { // 不连通则合并             fa[rootU] = rootV;             total += edges[i].w;             selected++;             if (selected == n - 1) break; // 已选够n-1条边         }     }      // 输出结果     if (selected == n - 1) cout << total << endl;     else cout << "-1" << endl; // 图不连通      return 0; }

时间复杂度 (O(n times alpha (n) )) ，空间复杂度 (O(n))

严格次小生成树（很难）

这个严格次小生成树的难度将会让初学者感到不易，其模板题难度为 NOI 难度，请估摸好自身实力，我们准备出发！
怎么求严格慈孝生成树呢？
说得简单一点：
假设我们有 (n) 个村庄，一共 (n-1) 座桥，此时一座桥被山洪给冲垮了，需要换上另一个不如这个桥却最优的桥。听懂上面这个故事了吗？没错，以上故事告诉了我们以下几个信息：

严格次小生成树与最小生成树之间至多有 (1) 条边的差距（证明会讲）。
严格次小生成树的实现方法相当于删除边，添加边，比较边的过程。
如何证明？当然 (2) 这个结论是毋庸置疑的，(1) 的证明如下：

证明方法：反证法
假设存在一棵严格次小生成树 $ T' $，其与MST $ T $ 至少有两条边不同。我们需要通过调整 $ T' $ 来构造一棵与 $ T $ 仅有一条边不同的生成树，且权值仍严格大于 $ T $。

步骤：

边集排序：
- 将 $ T $ 和 $ T' $ 的边分别按权值从小到大排序，记为 $ ET = {e_1, e_2, dots, e_{n-1}}$ 和 (ET' = {f_1, f_2, dots, f_{n-1}})
  。
- 找到第一个不同的边下标 $ k $，使得 $ e_k neq f_k $。根据Kruskal算法的性质，必有 $ we_k leq wf_k $。
引入环与替换：
- 将 $ e_k $ 加入 $ T' $，此时会形成一个环 $ C $。
- 根据MST的性质，环 $ C $ 中除 $ e_k $ 外的其他边权值均大于或等于 $ we_k $（否则 $ T $ 不是MST）。
- 删除环 $ C $ 中权值最大的边 $ f_i $（若 $ wf_i > we_k $），得到新生成树 $ T'' $。
  - 若 $ wf_i > we_k $，则 $ T'' $ 的权值 $ wT'' = wT' + we_k - wf_i $，且 $ wT < wT'' < wT' $，这与 $ T' $ 是严格次小生成树矛盾。
  - 若 $ wf_i = we_k $，则 $ wT'' = wT' $，此时 $ T'' $ 与 $ T' $ 权值相同，但差异边数减少。重复此操作，最终可得到一棵与 $ T $ 仅有一条边不同的严格次小生成树。
唯一性保证：
- 若存在多条边差异，总能通过上述替换操作逐步减少差异边数，同时保证权值严格大于MST。

结论

通过反证法可知，严格次小生成树 $ T' $ 必须与MST $ T $ 仅有一条边不同，否则会导出矛盾或构造出更优的生成树。

综上，我们可以得知，要么不存在严格次小生成树，要么就满足以上两条约束。
接下来就是实现方法的探讨了，我们知道，因为 MST 与 SSMST（Strictly Second Minimum Spanning Tree，严格次小生成树）之间只有一条边的差距，因此我们可以尝试枚举对于每一条非树边，加入到最小生成树中使其构成环路，然后删除掉这个环中的最大者（如果添加的那条变得权值和最大者相同，则删除次大者），这个过程可能需要LCA优化，因为我们添加边之前，最小生成树的次大值和最大值也可以用树上倍增的方法维护，定义 (max_{i,j}) 为 (i) 向上 (2^j) 的最大值，(max2_{i,j}) 为 (i) 向上 (2^j) 的次大者，此时就需要分类讨论了，得到最终代码如下：

        for(int j=1;j<=LOG;j++){             fath[v][j]=fath[fath[v][j-1]][j-1];             int tmp[4]={max1[v][j-1],max1[fath[v][j-1]][j-1],max2[v][j-1],max2[fath[v][j-1]][j-1]};             sort(tmp,tmp+4,greater<int>());             max1[v][j]=tmp[0];             max2[v][j]=LLONG_MIN;             for(int i=1;i<4;i++){                 if(tmp[i]<tmp[0]){                     max2[v][j]=tmp[i];                     break;                 }             }         }

然后用LCA来找环上的最大者和次大者，最后和答案作比较，我们的代码就出来了！

Code

#include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 3e5+100; struct node{     int u,v;     int w;     bool vis;     bool operator < (const node &a)const{         return w<a.w;     } }edge[maxn]; int fath[maxn][20],dep[maxn],max1[maxn][20],max2[maxn][20],n,m,LOG,fa[maxn]; vector<vector<pair<int,int>>>tree; int find(int x){     if(fa[x]==x)return x;     return fa[x]=find(fa[x]); } bool join(int x,int y){     int fx=find(x);     int fy=find(y);     if(fx!=fy){         fa[fx]=fy;         return true;     }     return false; } int kruskal(){     sort(edge+1,edge+1+m);     for(int i=1;i<=n;i++)fa[i]=i;     int cnt=n,sum=0;     for(int i=1;i<=m;i++){         if(cnt==1)break;         if(join(edge[i].u,edge[i].v)){             cnt--;             sum+=edge[i].w;             edge[i].vis=true;             tree[edge[i].u].push_back({edge[i].v,edge[i].w});             tree[edge[i].v].push_back({edge[i].u,edge[i].w});         }     }     return sum; } void dfs(int u,int fa){     for(auto i : tree[u]){         int v=i.first;         int w=i.second;         if(v==fa)continue;         dep[v]=dep[u]+1;         fath[v][0]=u;         max1[v][0]=w;         max2[v][0]=LLONG_MIN;         for(int j=1;j<=LOG;j++){             fath[v][j]=fath[fath[v][j-1]][j-1];             int tmp[4]={max1[v][j-1],max1[fath[v][j-1]][j-1],max2[v][j-1],max2[fath[v][j-1]][j-1]};             sort(tmp,tmp+4,greater<int>());             max1[v][j]=tmp[0];             max2[v][j]=LLONG_MIN;             for(int i=1;i<4;i++){                 if(tmp[i]<tmp[0]){                     max2[v][j]=tmp[i];                     break;                 }             }         }         dfs(v,u);     } } pair<int,int> query(int u,int v){     int ans1=LLONG_MIN,ans2=LLONG_MIN;     if(dep[u]<dep[v])swap(u,v);     for(int k=LOG;k>=0;k--){         if(dep[fath[u][k]]>=dep[v]){             if(max1[u][k]>ans1){                 ans2=ans1;                 ans1=max1[u][k];             }else if(max1[u][k]<ans1&&max1[u][k]>ans2){                 ans2=max1[u][k];             }             if(max2[u][k]>ans2){                 ans2=max2[u][k];             }             u=fath[u][k];         }     }     if(u==v)return {ans1,ans2};     for(int k=LOG;k>=0;k--){         if(fath[u][k]!=fath[v][k]){             if(max1[u][k]>ans1){                 ans2=ans1;                 ans1=max1[u][k];             }else if(max1[u][k]<ans1&&max1[u][k]>ans2){                 ans2=max1[u][k];             }             if(max2[u][k]>ans2){                 ans2=max2[u][k];             }             if(max1[v][k]>ans1){                 ans2=ans1;                 ans1=max1[v][k];             }else if(max1[v][k]<ans1&&max1[v][k]>ans2){                 ans2=max1[v][k];             }             if(max2[v][k]>ans2){                 ans2=max2[v][k];             }             u=fath[u][k];             v=fath[v][k];         }     }     if(max1[u][0]>ans1){         ans2=ans1;         ans1=max1[u][0];     }else if(max1[u][0]<ans1&&max1[u][0]>ans2){         ans2=max1[u][0];     }     if(max1[v][0]>ans1){         ans2=ans1;         ans1=max1[v][0];     }else if(max1[v][0]<ans1&&max1[v][0]>ans2){         ans2=max1[v][0];     }     if(max2[u][0]>ans2)ans2=max2[u][0];     if(max2[v][0]>ans2)ans2=max2[v][0];     return {ans1,ans2}; } signed main(){     cin>>n>>m;     LOG=log2(n);     tree.resize(n+1);     for(int i=1;i<=m;i++){         int u,v,w;         cin>>u>>v>>w;         if(u==v)continue;         edge[i]={u,v,w,false};     }     int sum=kruskal();     dep[1]=1;     dfs(1,0);     int sec=LLONG_MAX;     for(int i=1;i<=m;i++){         if(!edge[i].vis){             pair<int,int>tmp=query(edge[i].u,edge[i].v);             if(edge[i].w>tmp.first){                 sec=min(sec,sum+edge[i].w-tmp.first);             }             if(edge[i].w>tmp.second && tmp.second!=LLONG_MIN){                 sec=min(sec,sum+edge[i].w-tmp.second);             }         }     }     cout<<sec; }

由于难度较大，代码是本人亲自写的，代码风格可能不好看，敬请谅解。

发表评论