核心结论 #

你的教授的说法不准确——带权图可能存在多个最小生成树，算法输出的唯一性不等于图中MST的唯一性。

两种关键场景分析 #

1. 所有边权重唯一时：MST确实唯一 #

如果图中每条边的权重都不重复，那么无论使用Kruskal还是Prim算法，也不管边的处理顺序如何，最终生成的MST都是唯一的。因为任何替换边都会导致总权重增加，不存在其他符合“总权重最小”的生成树。

2. 存在相同权重的边时：可能存在多个MST #

当图中有多条边权重相同时，就可能出现多个总权重相等的生成树，它们都满足MST的定义（总权重最小，且是连通无环的子图）。

举个简单例子：
假设图有4个节点A、B、C、D，边包括：

• A-B（权重1）、C-D（权重1）
• B-C（权重2）、A-D（权重2）、A-C（权重2）

此时可以生成两个不同的MST：

• 选择A-B、B-C、C-D，总权重为1+2+1=4
• 选择A-B、A-D、C-D，总权重同样为1+2+1=4

这两个都是合法的MST，总权重一致但结构不同。

关于教授提到的“固定处理顺序后输出唯一” #

教授所说的“按权重升序（字母节点按字母序）处理后仍仅生成唯一MST”，指的是在固定边处理规则下，算法会输出确定的一个MST，但这并不代表图中不存在其他MST。

比如Kruskal算法在遇到同权重边时，按字母序优先选择节点名称靠前的边，会得到一个固定结果，但图中可能还有其他符合条件的MST，只是算法按照设定规则选择了其中一个而已。

总结 #

• 只有当图中所有边权重唯一时，MST才是唯一的；
• 存在同权重边时，图中可能存在多个MST，算法的固定处理顺序只会让输出唯一，但不否定其他MST的存在。

内容的提问来源于stack exchange，提问作者Muhammad Ammar Khalid