最小生成树

无向连通带权图的生成树连接全部 n 个顶点且恰有 n-1 条边；最小生成树（MST）使总边权最小。图不连通时得到最小生成森林。

Kruskal

按边权从小到大枚举，若两端属于不同连通块就选边并合并集合。并查集实现“是否成环”的判定；利用切分性质，当前能连接两个块的最轻边可安全加入。

sort(e.begin(),e.end()); long long ans=0; int cnt=0;
for(auto [w,u,v]:e) if(find(u)!=find(v)){
  parent[find(u)]=find(v); ans+=w; if(++cnt==n-1) break;
}

Prim

从任意点开始，每次选连接已选集合与未选集合的最轻边。邻接表配最小堆，堆中可保留过期条目，取出时跳过已访问点即可。

MST 不一定唯一；权值相同的边可产生不同树，但最小总权相同。整理自 XOJ《最小生成树》。