同一图中两个不同最小生成树的边权重是否必须对应相同？

嘿，这个问题问到点子上了——答案是肯定的，而且其实还有个更强的结论：同一幅图的任意两个最小生成树，每种权重的边的数量都是完全相等的。

为什么会这样？ #

我们可以用Kruskal算法的执行逻辑来理解：

• Kruskal算法按边的权重从小到大依次处理，每次选择不会形成环的边加入MST。
• 当处理到某一权重w的边时，此时图的连通分量状态是固定的——因为所有比w小的边已经处理完毕，不管之前在低权重阶段选了哪些边，当前的连通分量数量和结构不会改变。
• 这意味着，在处理权重w的边时，我们能选出的边的数量是固定的：等于「处理前的连通分量数」减去「处理后的连通分量数」。

换句话说，不管你怎么选择符合条件的权重w的边，最终生成的MST里，权重为w的边的数量都是一样的。

举个直观的例子 #

假设我们有一个四边形图，顶点为A、B、C、D，边的权重如下：

• AB=1，BC=1，AC=1
• CD=2，DA=2

第一个MST可以选AB、BC、CD（总权重1+1+2=4），其中包含2条权重1的边，1条权重2的边。
第二个MST可以选AB、AC、DA（总权重1+1+2=4），同样包含2条权重1的边，1条权重2的边。

你看，第一个MST里的每个权重值（1和2），在第二个MST里都有对应数量的同权重边存在。

总结 #

回到你的问题：第一个MST中每条边的权重，在第二个MST里必然存在相同权重的边（而且数量完全匹配）。不存在某个权重的边只出现在其中一个MST里的情况。

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