最小生成树

什么是最小生成树

在一张带权无向连通图 $G=(V,E,w)$ 中,最小生成树(Minimum Spanning Tree, MST)是连接所有顶点、且边权和最小的一棵生成树(含 $|V|-1$ 条边、无环).若图不连通,则对应为最小生成森林.

性质

• 割性质(Cut Property):任取把顶点分成两部分的割,跨越该割的最轻边一定属于某个 MST.

• 环性质(Cycle Property):任取一个环,其中的最重边不属于任何 MST.

• 最小瓶颈:任一 MST 同时也是最小瓶颈生成树(最大边权尽可能小).

• 唯一性:若所有边权互不相同,MST 唯一.

• 权值平移/缩放:边权统一加同一常数或乘正数,不改变 MST 结构.

• 允许负边:允许负权,算法与性质不变(只要图无向且可连通).

Kruskal算法

这是Kruskal算法的核心思想

“按权值从小到大选边，能连就连，成环就跳过。”

至于为什么要成环就跳过,因为生成树不能有环,而且一旦出现环,总权值不会变小,只会变大,如果非要证明我要引用一下

给定无向连通图 $G=(V,E,w)$。我们证明“成环的边中，最重的那一条不属于某棵最小生成树（至多在权值并列时可被任意一条同重边替换），因此对按从小到大扫边的 Kruskal 来说，遇到会成环的边直接丢弃不劣；等价地，若为了连通性加入一条边导致出现环，那么把环里的一条更重边删掉，总权值不会变小，只会变小或相等”。证明（交换论证）：取任意一条简单环 $C\subseteq E$，令 $e\in C$ 满足 $w(e)\ge w(x)$ 对所有 $x\in C$。若存在一棵最小生成树 $T$ 不含 $e$，结论对这条 $e$ 已证；若所有最小生成树都含 $e$，取其中一棵 $T$ 并考察 $C$。由于 $C$ 是环，$C\setminus\{e\}$ 在图中将 $e$ 的两个端点重新连通；把 $e$ 从 $T$ 中删去得到森林 $T-e$（两连通分量），环上必存在一条边 $f\in C\setminus\{e\}$ 横跨这两个分量（否则环无法闭合）。将 $f$ 加回去得 $T'=(T-e)\cup\{f\}$，它仍是生成树；并且 $w(T')=w(T)-w(e)+w(f)\le w(T)$。若 $w(f)<w(e)$，则 $w(T')<w(T)$，与 $T$ 的最小性矛盾；故只能有 $w(f)=w(e)$，此时 $T'$ 也是最小生成树，且不含 $e$。于是对任意环，其最重边总可以被剔除而不劣（权值严格劣或相等），这叫“环性质”。Kruskal 每次从未选边里取当前最小权值且不成环的边，若某条候选边在当下会与已选边构成环，则它属于某个环且不比环上别的边轻，按上面的结论它不必进入任何最优解，直接跳过不影响可达到的最小总权值。因此 Kruskal 的“成环就跳过”是安全且保持最优的；同理，从一棵树额外加一条边一定形成唯一环，若你坚持保留这条新增边，就必须从该环删去别的边以回到树结构，而为了使总权值不增加，理性选择是删去环中不轻于它的边（最重者），因此“出现环并作合理消解后，总权值不变或变小；若你误把较轻的删了、把较重的留下，总权值只会变大”。综上，生成树本身无环，而在构造过程中“成环即弃”的策略保证了总权值非增，最终得到最小生成树。

算法流程

1. 读入 n 个点、m 条边，边是三元组 (u,v,w)。

2. 按 w 升序排序所有边。

3. 初始化并查集 DSU：parent[i]=i，size[i]=1，已选边数 cnt=0，答案权值和 ans=0。

4. 依次扫描排序后的每条边 (u,v,w)：

   • 做 fu=find(u),fv=find(v)；

   • 若 fu!=fv：把这条边加入生成树：ans+=w，union(fu,fv)，cnt++；

   • 若 fu==fv：跳过（会成环）。

5. 当 cnt==n-1 时停止；输出 ans 与边集。

6. 若扫完仍 cnt<n-1，原图不连通，仅得到最小生成森林（或按题意报错/提示）。

这本质上是一个贪心的思想,非常易于理解

#include<bits/stdc++.h>
using namespace std;
struct E{int u,v,w;};
int fa[100005],s[100005];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool unite(int a,int b){
    a=find(a);b=find(b);
    if(a==b)return 0;
    if(s[a]<s[b])swap(a,b);
    fa[b]=a;s[a]+=s[b];
    return 1;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    vector<E> e(m);
    for(int i=0;i<m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e.begin(),e.end(),[](E a,E b){return a.w<b.w;});
    for(int i=1;i<=n;i++)fa[i]=i,s[i]=1;
    long long ans=0;int cnt=0;
    for(auto &x:e){
        if(unite(x.u,x.v)){
            ans+=x.w;
            if(++cnt==n-1)break;
        }
    }
    if(cnt<n-1)cout<<"No MST\n";
    else cout<<ans<<"\n";
}

Prim算法

核心思想

1. 从任意一个起点开始，把它加入生成树集合 T。

2. 每次选择 T 内的点 与 T 外的点 之间权值最小的边，把这条边和它连接的那个新点加进 T。

3. 重复这个过程，直到所有点都在 T 里。

执行流程

• 选一个起点 → 入堆 (0, start)

• 循环直到堆空：

  • 弹出堆顶 (w,u)

  • 如果 u 已访问 → 跳过

  • 否则加入 MST，累加权值

  • 遍历 u 的所有边 (u,v,w) → 如果 v 未访问 → 入堆 (w,v)

• 直到所有点都加入 MST。

类似 Dijkstra

#include<bits/stdc++.h>
using namespace std;
struct E{int v,w;};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    vector<vector<E>> g(n+1);
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    vector<int> vis(n+1,0);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.push({0,1});
    long long ans=0;int cnt=0;
    while(!pq.empty()){
        auto [w,u]=pq.top();pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        ans+=w;
        cnt++;
        for(auto &e:g[u])if(!vis[e.v])pq.push({e.w,e.v});
    }
    if(cnt==n)cout<<ans<<"\n";
    else cout<<"impossible\n";
}

总结(GPT-5生成)