生成树
参考资料
最小生成树
无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。
算法对比
代表图的点数， 代表图的边数。
| 算法名称 | 时间复杂度 |
|---|---|
| Kruskal 算法 | |
| Prim 算法 | |
| Boruvka 算法 |
Kruskal 算法
Kruskal 是贪心算法：把所有边按权升序排序，依次尝试加入，用并查集判断两端点是否已连通，不连通才加入这条边。加满 条边即得最小生成树。时间复杂度为 。
struct Edge
{
int u,v,w;
bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n)
{
for(int i=1;i<=n;i++)fa[i]=i;
sort(E.begin(),E.end());
int ans=0,cnt=0;
for(auto [u,v,w]:E)
{
if(cnt==n-1)break;
int x=find(u),y=find(v);
if(x==y)continue;
fa[x]=y;
ans+=w;
cnt++;
}
return cnt==n-1?ans:-1;
}
最小树形图
最小树形图 是有向图中以某点为根、所有点都能从根到达的最小权外向生成树。朱刘算法（Chu–Liu / Edmonds）反复为每个非根点选一条最小入边，若选出的边构成环就把环缩成一点并调整入边权后递归，复杂度 。
瓶颈生成树
瓶颈生成树 是使最大边权最小的生成树。无向连通图的最小生成树一定是瓶颈生成树。
Kruskal 重构树
Kruskal 重构树 在 Kruskal 加边时不直接合并两点，而是新建一个权值为当前边权的虚点，作为两个连通块代表元的父亲。最终得到一棵二叉树：原图的点为叶子，虚点权值满足大根堆性质，两叶子路径上的最大边权恰为其 LCA 的权值。常用于处理「只经过边权不超过 的边」一类可达性问题。
struct Edge
{
int u,v,w;
bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
vector<int> G[N];
int fa[N],val[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n)
{
for(int i=1;i<=n<<1;i++)fa[i]=i;
sort(E.begin(),E.end());
int cnt=0,t=n;
for(auto [u,v,w]:E)
{
if(cnt==n-1)break;
int x=find(u),y=find(v);
if(x==y)continue;
fa[x]=fa[y]=++t;
G[t].push_back(x);
G[t].push_back(y);
val[t]=w;
cnt++;
}
return t;
}