最小生成树

生成树从原图删除所有环，却保留全部顶点之间的连通性；MST 再在这些骨架中比较边权总和。割性质从“任何连接方案都必须跨过这道边界”寻找可加入边，环性质从“圈上总有一条边可以删”寻找可排除边。两者是同一个交换动作的正反视角。

贪心过程应保持的是“已选森林能够扩充成某棵 MST”，而不仅是“现在没有环”。许多没有环的边集已经选入过贵边，无法完成为最优树。尊重当前森林的割保证交换时不会删掉已承诺保留的边；因此每一步都保留至少一个最优完成方案，最后选满 $|V|-1$ 条边时便已经是其中之一。

目标函数只把所选边各计一次，不关心某条边会出现在多少对顶点的树路径中。因此一棵总造价最小的网络骨架，未必给任何指定根提供最短路线，也不自动具有冗余或容错能力。

三角形的边权为 $1,2,4$ 时，取权 $1,2$ 两边得到总权 $3$；权 $4$ 的边在唯一圈中严格最重，不可能进入 MST。若三条边都为 $1$，删去任意一条都得到总权 $2$ 的 MST，说明平局会造成多解。所有边权互异时 MST 唯一；反命题不成立，含相等权边的图也可能因结构限制只有一棵 MST。

全局排序为何还要检查分量 ​

设四个顶点的边为 $ab:1,bc:2,ac:3,cd:4,bd:5$。Kruskal 算法理路Kruskal 算法Kruskal's algorithm按边权递增加入不成环边并用并查集维护连通分量的最小生成树算法。先选 $ab,bc$，此时森林分量为 $\{a,b,c\}$ 与 $\{d\}$；权重 $3$ 的 $ac$ 虽是下一条最便宜的边，却连接同一分量，必须跳过。随后选 $cd$，得到总权 $7$ 的树。排序负责寻找便宜候选，分量检查负责保证候选跨越尊重当前森林的割，两个步骤缺一不可。

在比较与并查集操作的常用模型下，排序花费 $O(m\log (m+1))$，分量查询与合并的总摊还成本为 $O(m\alpha (n))$。$n\ge 2$ 时，对于简单连通图可将主界写成 $O(m\log n)$；若允许任意多条平行边，应保留 $m$ 或说明预处理，不能无条件利用 $m\le n^2$。

负权边不会导致无界下降，因为任何生成树固定只含 $|V|-1$ 条边；贪心证明也只比较边权。平行边应作为独立候选，较重的同端点平行边构成长度为二的多重图圈并可排除；自环不可能属于生成树。若基础文件格式只表示简单图，应在读入时明确合并平行边或保留边 ID，不能默默覆盖。

单顶点图的 MST 是空边集，权重为零；零顶点图按生成树条目的约定只输出空生成森林。图不连通时不存在覆盖全部顶点的生成树。对每个连通分量分别最小化，得到最小生成森林；若有 $c$ 个分量，森林含 $|V|-c$ 条边。有向图的对应问题需要指定根与入弧方向，称为最小树形图，并不由无向割性质直接解决。

MST 与最短路理路最短路问题Shortest-path problem在有限有向实权图中寻找源点到各顶点的最小有向游走成本。在非负权图上仍可不同。若 $w(sa)=2,w(ab)=2,w(sb)=3$，MST 取 $sa,ab$，总权 $4$；从 $s$ 出发却会沿直边 $sb$ 以成本 $3$ 到达 $b$，而 MST 中的路线成本为 $4$。相应的最短路树取 $sa,sb$，总权 $5$。

在网络布线中，边权可表示铺设一段链路的成本，MST 给出无冗余连通骨架；若系统还要求故障容错，就要增加边连通约束，MST 本身不够。单链接聚类按边权从小到大合并分量，截断 Kruskal 过程可得到指定簇数；这一解释依赖权重是可比较的不相似度。

任意 MST 也是最小瓶颈生成树：若有另一棵树的最大边更轻，可在 MST 最大边诱导的割上找到更轻替换边，矛盾；最小瓶颈树反过来未必最小化总权。边权更新后，删除一条树边需要在新割上寻找替代边，动态 MSF理路动态最小生成森林Dynamic minimum spanning forest · Dynamic MSF · Fully dynamic MST在无向带权图的边插入与删除之间持续维护每个连通分量的最小生成树，并以最轻跨割替代边恢复最优森林。因此是另一个带更新接口的问题，静态交换性质只提供正确性工具，不给出更新时间界。