MST算法边权重变更疑问：为何调整A-B边权重会影响其MST归属？

嘿，这个问题刚好触及了最小生成树（MST）的核心规则，咱们一步步把它讲明白：

核心原理：MST中边的留用条件 #

一条边能留在MST里的关键是：它是连接其两个端点所在连通分量的「最优选择」——换句话说，不存在任何一条不经过这条边的路径，能以更优的方式把这两个分量连起来。更精准的表述是：

边(u, v)属于某个MST，当且仅当它的权重 ≤ u和v之间所有不含该边的路径中，路径内的最大边权重。

为啥是「路径内的最大边权重」？因为如果用这条替代路径连接u和v，路径里的每条边要么已经在MST中，要么可以被选入MST；当你提高(u, v)的权重时，只要它不超过这个最大边权重，用这条边仍然比用替代路径更划算（毕竟替代路径里至少有一条边和它权重相等或更大，整体总权重不会更低）。

对应到你的例子 #

回到A-B边的情况：

• 当你给它增加1.5、4.5或7.5时，调整后的权重仍然≤A、B之间所有替代路径的最大边权重。这时候A-B还是连接两个分量的最优选择，所以它会留在MST里（甚至当权重刚好等于临界值时，可能存在多个MST，A-B依然是其中一个的组成部分）。
• 当你增加10.5时，调整后的权重超过了这个临界值（也就是替代路径里的最大边权重）。此时用那条替代路径连接A和B，总权重会比用变贵后的A-B更小，所以A-B就不再属于任何MST了。

举个具象的例子辅助理解：假设原A-B权重是5，A到B的替代路径是A-C-B，其中A-C权重是8，C-B权重是9，这条路径的最大边权重是9。那么A-B的权重最多可以增加到9（5+4=9），超过9之后（比如5+5=10），Kruskal算法在排序时，A-C和C-B会先于A-B被选中，等轮到A-B时，A和B已经连通了，所以A-B会被跳过，不会加入MST。

总结 #

本质上，每条MST边都有一个「权重增长临界值」，这个值等于它两个端点之间所有不含该边的路径中的最大边权重。只要边的权重不超过这个临界值，它就还是连接两个分量的最优选择；一旦超过，就会被更优的替代路径取代，从而退出MST。

内容的提问来源于stack exchange，提问作者user8756425