属于该分类的文章：

最小生成树问题

3篇文章

Prim 算法

Prim 是求解最小生成树的算法，从任意顶点出发维护一个已选顶点集合，每次选取连接集合内外、权值最小的边，将对应顶点并入集合，直到包含全部顶点；朴素实现 O(n^2) 适合稠密图，堆优化版本 O(mlog n) 适合稀疏图，支持负权边。

Kruskal 是求解最小生成树的算法，核心思路是将全部边按权值从小到大排序，依次选取边，借助并查集判断边的两个端点是否属于不同连通块，若不连通就把这条边加入生成树，直到选出 n‑1 条边；适合稀疏图，时间复杂度主要由排序决定 O(mlog m)，可以处理带负权的边。

最小生成树两大理论基础：1. 切分性质：任意割的权值最小割边，必属于某棵最小生成树，是 Prim 算法的依据。2. 环性质：任意环中权值最大的边，一定不在最小生成树里，支撑 Kruskal 算法。连通加权无向图才存在最小生成树，总权值和唯一，可有多棵不同最小生成树。