图
最小生成树
给定一个连通的、带权的无向图，最小生成树（MST）就是把所有顶点连成一体的最省办法。设想你要铺设电缆，让镇上每户人家都接入同一个网络，而你希望电缆总长度最小。答案就是一棵 MST：它触及每一个顶点，用的边一根都不多，构成一棵树（V 个顶点恰由 V-1 条边相连、没有环），且总权重尽可能小。
有两种经典的贪心算法能求出它。Kruskal 算法把所有边从便宜到贵排序，只要某条边不会造成环就把它加入，直到全部连通为止。Prim 算法从一个起始顶点开始让树生长，反复加入“能接到尚未在树中的顶点”的最便宜那条边。两者都依赖同一个洞见：从“已建好的部分”跨向“其余部分”的最小那条边，总是可以安全地选取。
它们的开销相近：Kruskal 约为 O(E log E)（主要花在给边排序上），用优先队列实现的 Prim 约为 O((V + E) log V)。注意 MST 最小化的是“连接总成本”，这和最短路径是不同的目标——MST 一般并不是“让每一对顶点各自取得最短距离”的那种路线。
sort(edges.begin(), edges.end()); // by weight
for (auto [w, u, v] : edges) {
if (find(u) != find(v)) { // no cycle
unite(u, v);
total += w; // edge in MST
}
}并查集能廉价地判断两个端点是否已经连通。
只有连通图才有 MST；对非连通图，得到的是最小生成森林，每个连通分量一棵树。
又称
另见