最小生成树是什么
在一个连通无向带权图中，最小生成树是指
- 一个子图，它是一棵树（无环、连通）
- 包含原图的所有顶点
- 所有边的权重之和最小
Prim
加点法
从任意一个顶点开始，每次选择一条连接已选顶点集和未选顶点集的最小权边，并将该边连接的顶点加入已选集。逐步扩张，直到包含所有顶点。
算法步骤
- 随机选择一个起始顶点，加入集合 UU（已选顶点集）。
- 在所有连接 UU 内顶点和 UU 外顶点的边中，选择一条权重最小的边 (u,v)(u, v)（其中 uu 在 UU 中，vv 不在 UU 中）。
- 将顶点 vv 加入集合 UU ，边 (u,v)(u, v) 加入最小生成树。
- 重复步骤2、3，直到 UU 包含所有顶点。
时间复杂度
- 使用邻接表 + 二叉堆 O(ElogV)O(E log V)
- 使用斐波那契堆可优化至 O(E+VlogV)O(E + V log V)
code
void prim(){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push({0,1});
while(!q.empty()&&cnt<n){
int d=q.top().first,u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=1;
sum+=d;
cnt++;
for(int i=head[u];i;i=E[i].nxt){
int v=E[i].to,w=E[i].w;
if(w<dis[v]) dis[v]=w,q.push({w,v});
}
}
}
例子
2
A ----- B
| |
3| |1
| |
C ----- D
4
从A开始
- 选边 (A,B,2)，加入 B
- 选边 (B,D,1)，加入 D
- 选边 (A,C,3)，加入 C MST总权重 2+1+3=62 + 1 + 3 = 6
Kruskal
加边法
将所有边按权重从小到大排序，每次选择一条最小的边，如果加入这条边不会形成环，就将其加入生成树。
算法步骤
- 将图中所有边按权重从小到大排序。
- 初始化一个空的最小生成树。
- 按权重从小到大遍历每条边（如果当前边连接的两个顶点不在同一个连通分量中（即加入后不会形成环），则将该边加入生成树，并合并这两个连通分量）
- 直到生成树中有V−1V-1条边为止。
实现关键
- 使用并查集数据结构来高效地判断是否形成环（即检查两个顶点是否属于同一集合）。
- 需要对所有边进行排序。
时间复杂度
- 排序边 O(ElogE)O(E log E)
- 并查集操作（路径压缩+按秩合并）近似 O(α(V))O(α(V))，几乎为常数
- 总复杂度 O(ElogE)O(E log E) 或 O(ElogV)O(E log V)（因为E最多为V²）
code
int fa[N],n,m; //用来实现并查集，记录每个顶点的祖宗顶点
struct Edge{
int a,b,w;
friend bool operator < (Edge a,Edge b){
return a.w<b.w;
}
}E[M];
int find(int u){//寻找祖宗顶点，并且路径压缩
if(u==p[u]) return u;
return p[u]=find(p[u]);
}
int kruskal(){
sort(E,E+m); //将边按照边权大小排序
iota(fa+1,fa+n+1,1);//对fa[]数组初始化，一开始每个顶点的祖宗都是自己
int sum=0,cnt=0; //记录最后的答案，即最小生成树的所有边的边权;记录连通部分有多少边，方便最后判断图是否连通
for(int i=0;i<m;i++){//遍历每一条边
int a=E[i].a,b=E[i].b,w=E[i].w;
a=find(a),b=find(b); //找到边的两个顶点的祖宗（看俩个顶点是否属于一个集合）
if(a!=b){//如果祖宗不同，也就是不在一个集合
sum+=w;
cnt++; //连通部分的边数加一
p[a]=b; //把a的祖宗置为b
}
}
if(cnt<n-1) return 0x3f3f3f3f;//如果最后连通部分的边数小于n-1，就说明图不连通
else return res;
}
例子
2
A ----- B
| |
3| |1
| |
C ----- D
4
边排序后(B,D,1), (A,B,2), (A,C,3), (C,D,4)
- 选(B,D,1)，无环，加入
- 选(A,B,2)，无环，加入
- 选(A,C,3)，无环，加入
- 已选3条边（V=4，边数已够），停止。MST总权重 1+2+3=61+2+3=6
对比
| 特性 | Prim算法 | Kruskal算法 |
|---|---|---|
| 核心思想 | 加点（从一点开始扩张） | 加边（按权重从小到大选） |
| 数据结构 | 优先队列 | 并查集、需排序所有边 |
| 时间复杂度 | O(ElogV)O(E log V) | O(ElogE)O(E log E) |
| 适用图 | 稠密图（边多顶点少） | 稀疏图（边少顶点多） |
| 过程特点 | 始终维护一棵连通的树 | 中间过程可能是多棵树的森林 |
| 起始点 | 需要指定一个起始点 | 不需要起始点，全局考虑边 |