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

小侃發表於 2025-4-30 21:01:00

<h2 id="最小生成树">最小生成树</h2>
<h3 id="何为最小生成树">何为最小生成树？</h3>
有一类问题：给定一张图，可以删除若干条边，在不改变连通性（一般是全联通）的情况下，权值和最小的方案是什么？没错，这就是最小生成树问题（MST问题）。那么基本性质其实连聪明的小学生都能看出来，应当使得最后留下 $n-1$ 条边且没有环路得到情况下才有可能构成生成树，这便是Kruskal的基本实现原则，这个后面会讲。
<h3 id="最小生成树的prim算法">最小生成树的Prim算法</h3>
其实Prim本身还是比较好理解的，跟Dijstra没什么两样，方法如下：
<ul>
<li>随便选一个结点出发，一般选定节点编号为 $1$，标记为 $now$，但请注意：只有在图全联通的情况下才能这么做。</li>
<li>向当前节点能够走到的所有节点进行搜索，如果当前 <code>dis</code> 值小于对于当前 $now$ 的更新后的节点最大值，那就更新 <code>dis</code>，并记录下此节点。</li>
<li>当遍历完 $now$ 所有能去到的节点之后，留下的就是对于更新后的，对于 $now$ 能走到的节点权值最小值的编号，将其列为访问过，并计入到最小生成树中。</li>
<li>访问这个被记入访问了的节点，并重复 $2$ 到 $3$ 步直到推出结果。 
为什么这个算法可行呢？</li>
</ul>
<ol>
<li>首先我们确保了每次选中的变得权值是最小的。</li>
<li>由于每个节点至多且一定会被选中 $1$ 次，所以就会被选中 $n-1$ 条边（最后一次更新没有选边）。 
和上述我们面熟的的最小生成树的定义一样一样的，恭喜你，学会了Prim算法。对于其时间复杂度，是 $O(n^2)$ （$n$ 为节点数），空间复杂度是 $O(n)$ ，非常稳定，（唯一的缺点就是慢）。</li>
</ol>
<h4 id="code">Code:</h4>
<pre><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;
}
</code></pre>
<h3 id="堆优化prim算法">堆优化Prim算法</h3>
既然Prim那么慢，有没有什么好方法来优化掉这个致命的问题呢？当然有，我们可以使用优先队列来优化掉这个Prim算法。 
思考：既然每次选点我们都只选最小的那个节点，而并不关心别的节点怎么了（<s>看来图论的世界也只容得下第一名啊</s>），欸，刚好和我们优先队列一拍即合，没错，他们两个需要维护的东西完全一致，那么就用堆来优化Prim好了：
<ol>
<li>首先我们创建一个 <code>priority_queue</code>，且是小根堆。</li>
<li>把 $now$ 压入队列。</li>
<li>弹出队首，叫做 $cur$ 。</li>
<li>检查 $cur$ 是不是已经被访问过，如果是，就跳过。</li>
<li>遍历 $cur$ 能抵达的所有节点，执行上述根性操作并push。 
6.重复 $2$ ~ $5$ 步，直到我们求出MST。 
其实堆优化Prim不是一种模板，是一种思想，就是要学会怎么找到题目中可以优化掉的没有用的信息，看有没有合适的优化方法，这种思想就是这么多高级算法的最终的最终的源头。</li>
</ol>
<h4 id="code-1">Code</h4>
<pre><code class="language-cpp">#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; // 邻接表存储图
int dist; // 存储顶点到MST的最小距离
bool visited; // 标记顶点是否已在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 = 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) continue;
 visited = true;
 totalWeight += d;
 selected++;

 for (auto &edge : adj) {
 int v = edge.second;
 int w = edge.first;
 if (!visited && w < dist) {
 dist = w;
 pq.push({dist, 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.push_back({w, v});
 adj.push_back({w, u});
}

prim_heap();

return 0;
}
</code></pre>
时间复杂度 $O(m \log m)$,空间复杂度 $O(n)$ 。
<h3 id="kruskal-算法">Kruskal 算法</h3>
再次观察题目，有没有什么由价值的信息呢？我们发现，添加一条边的过程实际上和并查集合并的过程如出一辙！欸，我们又找到了思路，没错，可以用并查集来寻找最小生成树。过程如下：
<ol>
<li>初始化并查集，现在有 $n$ 个连通块和 $0$ 条边。</li>
<li>现在排序所有边，按权值来排。</li>
<li>遍历边集数组，合并对于第 $i$ 条边的起点和终点，合并成功的话就计入答案，直到连通块个数为 $1$。 
那么为什么这个方案可行呢？我们随便画张图就知道了：</li>
</ol>
<ul>
<li>首先，如果两个节点不属于一个集合，那么会合并两个联通块，连通块个数减少 $1$ 个。</li>
<li>如果两个节点本来就属于一个节点，意味着再加入一条边就会形成环，故不会发生这样的情况，合并失败。</li>
<li>最后，因为我们的边集数组是一个有序（递增）的数组，因此也不存在会浪费掉任意一条最小生成树上的边，结果是最优的。</li>
</ul>
<h4 id="code-2">Code:</h4>
<pre><code class="language-cpp">#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;

int fa; // 并查集父节点数组

// 并查集查找根节点（路径压缩）
int find(int x) {
return fa == x ? x : fa = find(fa);
}

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;

// 读入边
for (int i = 0; i < m; i++) {
 cin >> 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 << total << endl;
else cout << "-1" << endl; // 图不连通

return 0;
}
</code></pre>
时间复杂度 $O(n \times \alpha (n) )$ ，空间复杂度 $O(n)$
<h2 id="严格次小生成树很难">严格次小生成树（很难）</h2>
这个严格次小生成树的难度将会让初学者感到不易，其模板题难度为 <code>NOI</code> 难度，请估摸好自身实力，我们准备出发！ 
怎么求严格次小生成树呢？ 
说得简单一点： 
假设我们有 $n$ 个村庄，一共 $n-1$ 座桥，此时一座桥被山洪给冲垮了，需要换上另一个不如这个桥却最优的桥。听懂上面这个故事了吗？没错，以上故事告诉了我们以下几个信息：
<ol>
<li>严格次小生成树与最小生成树之间至多有 $1$ 条边的差距（证明会讲）。</li>
<li>严格次小生成树的实现方法相当于删除边，添加边，比较边的过程。 
如何证明？当然 $2$ 这个结论是毋庸置疑的，$1$ 的证明如下：</li>
</ol>
证明方法：反证法 
假设存在一棵严格次小生成树 $ T' $，其与MST $ T $ 至少有两条边不同。我们需要通过调整 $ T' $ 来构造一棵与 $ T $ 仅有一条边不同的生成树，且权值仍严格大于 $ T $。
<h3 id="步骤">步骤：</h3>
<ol>
<li>
边集排序：
<ul>
<li>将 $ T $ 和 $ T' $ 的边分别按权值从小到大排序，记为 $ ET = {e_1, e_2, dots, e_{n-1}}$和 $ET' = \{f_1, f_2, dots, f_{n-1}\}$ 
。</li>
<li>找到第一个不同的边下标 $ k $，使得 $ e_k \neq f_k $。根据Kruskal算法的性质，必有 $ we_k \leq wf_k $。</li>
</ul>
</li>
<li>
引入环与替换：
<ul>
<li>将 $ e_k $ 加入 $ T' $，此时会形成一个环 $ C $。</li>
<li>根据MST的性质，环 $ C $ 中除 $ e_k $ 外的其他边权值均大于或等于 $ we_k $（否则 $ T $ 不是MST）。</li>
<li>删除环 $ C $ 中权值最大的边 $ f_i $（若 $ wf_i > we_k $），得到新生成树 $ T'' $。
<ul>
<li>若 $ wf_i > we_k $，则 $ T'' $ 的权值 $ wT'' = wT' + we_k - wf_i $，且 $ wT < wT'' < wT' $，这与 $ T' $ 是严格次小生成树矛盾。</li>
<li>若 $ wf_i = we_k $，则 $ wT'' = wT' $，此时 $ T'' $ 与 $ T' $ 权值相同，但差异边数减少。重复此操作，最终可得到一棵与 $ T $ 仅有一条边不同的严格次小生成树。</li>
</ul>
</li>
</ul>
</li>
<li>
唯一性保证：
<ul>
<li>若存在多条边差异，总能通过上述替换操作逐步减少差异边数，同时保证权值严格大于MST。</li>
</ul>
</li>
</ol>
<h3 id="结论">结论</h3>
通过反证法可知，严格次小生成树 $ T' $ 必须与MST $ T $ 仅有一条边不同，否则会导出矛盾或构造出更优的生成树。
综上，我们可以得知，要么不存在严格次小生成树，要么就满足以上两条约束。 
接下来就是实现方法的探讨了，我们知道，因为 MST 与 SSMST（Strictly Second Minimum Spanning Tree，严格次小生成树）之间只有一条边的差距，因此我们可以尝试枚举对于每一条非树边，加入到最小生成树中使其构成环路，然后删除掉这个环中的最大者（如果添加的那条变得权值和最大者相同，则删除次大者），这个过程可能需要LCA优化，因为我们添加边之前，最小生成树的次大值和最大值也可以用树上倍增的方法维护，定义 $max_{i,j}$ 为 $i$ 向上 $2^j$ 的最大值，$max2_{i,j}$ 为 $i$ 向上 $2^j$ 的次大者，此时就需要分类讨论了，得到最终代码如下：
<pre><code class="language-cpp"> for(int j=1;j<=LOG;j++){
 fath=fath];
 int tmp={max1,max1],max2,max2]};
 sort(tmp,tmp+4,greater<int>());
 max1=tmp;
 max2=LLONG_MIN;
 for(int i=1;i<4;i++){
 if(tmp<tmp){
 max2=tmp;
 break;
 }
 }
 }
</code></pre>
然后用LCA来找环上的最大者和次大者，最后和答案作比较，我们的代码就出来了！
<h3 id="code-3">Code</h3>
<pre><code class="language-cpp">#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;
int fath,dep,max1,max2,n,m,LOG,fa;
vector<vector<pair<int,int>>>tree;
int find(int x){
if(fa==x)return x;
return fa=find(fa);
}
bool join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
 fa=fy;
 return true;
}
return false;
}
int kruskal(){
sort(edge+1,edge+1+m);
for(int i=1;i<=n;i++)fa=i;
int cnt=n,sum=0;
for(int i=1;i<=m;i++){
 if(cnt==1)break;
 if(join(edge.u,edge.v)){
 cnt--;
 sum+=edge.w;
 edge.vis=true;
 tree.u].push_back({edge.v,edge.w});
 tree.v].push_back({edge.u,edge.w});
 }
}
return sum;
}
void dfs(int u,int fa){
for(auto i : tree){
 int v=i.first;
 int w=i.second;
 if(v==fa)continue;
 dep=dep+1;
 fath=u;
 max1=w;
 max2=LLONG_MIN;
 for(int j=1;j<=LOG;j++){
 fath=fath];
 int tmp={max1,max1],max2,max2]};
 sort(tmp,tmp+4,greater<int>());
 max1=tmp;
 max2=LLONG_MIN;
 for(int i=1;i<4;i++){
 if(tmp<tmp){
 max2=tmp;
 break;
 }
 }
 }
 dfs(v,u);
}
}
pair<int,int> query(int u,int v){
int ans1=LLONG_MIN,ans2=LLONG_MIN;
if(dep<dep)swap(u,v);
for(int k=LOG;k>=0;k--){
 if(dep]>=dep){
 if(max1>ans1){
 ans2=ans1;
 ans1=max1;
 }else if(max1<ans1&&max1>ans2){
 ans2=max1;
 }
 if(max2>ans2){
 ans2=max2;
 }
 u=fath;
 }
}
if(u==v)return {ans1,ans2};
for(int k=LOG;k>=0;k--){
 if(fath!=fath){
 if(max1>ans1){
 ans2=ans1;
 ans1=max1;
 }else if(max1<ans1&&max1>ans2){
 ans2=max1;
 }
 if(max2>ans2){
 ans2=max2;
 }
 if(max1>ans1){
 ans2=ans1;
 ans1=max1;
 }else if(max1<ans1&&max1>ans2){
 ans2=max1;
 }
 if(max2>ans2){
 ans2=max2;
 }
 u=fath;
 v=fath;
 }
}
if(max1>ans1){
 ans2=ans1;
 ans1=max1;
}else if(max1<ans1&&max1>ans2){
 ans2=max1;
}
if(max1>ans1){
 ans2=ans1;
 ans1=max1;
}else if(max1<ans1&&max1>ans2){
 ans2=max1;
}
if(max2>ans2)ans2=max2;
if(max2>ans2)ans2=max2;
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={u,v,w,false};
}
int sum=kruskal();
dep=1;
dfs(1,0);
int sec=LLONG_MAX;
for(int i=1;i<=m;i++){
 if(!edge.vis){
 pair<int,int>tmp=query(edge.u,edge.v);
 if(edge.w>tmp.first){
 sec=min(sec,sum+edge.w-tmp.first);
 }
 if(edge.w>tmp.second && tmp.second!=LLONG_MIN){
 sec=min(sec,sum+edge.w-tmp.second);
 }
 }
}
cout<<sec;
}
</code></pre>
由于难度较大，代码是本人亲自写的，代码风格可能不好看，敬请谅解。 
来源：https://www.cnblogs.com/CheeseFunction/p/18856026

頁: [1]

琼殿技术论坛's Archiver

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