Kruskal 和 Prim 算法求出的最小生成树一定唯一吗？

结论

Kruskal 和 Prim 算法都不能保证最小生成树（MST）唯一。对于连通的带权无向图，如果所有边的权值互不相同，MST 一定唯一。边权有重复时，图中可能有多棵 MST，但重复权值本身并不意味着一定有多解。

排序依据是边权。顶点或边的字母顺序不是求 MST 的必要规则；权值相同时，可以用它来固定处理顺序，让算法稳定地返回一棵 MST。

为什么可能有多棵 MST

设有一个三角形图，三条边的权值都是 1。任意选择其中两条边，都能连接三个顶点，总权值也都是 2。因此，这个图有三棵不同的 MST。

边权并列时，算法可能有多个同样合适的选择。如果这些选择会形成不同的生成树，图中就有多棵 MST。如果图的结构限制了选择，MST 仍可能唯一。

Kruskal 和 Prim 如何处理

• Kruskal 按边权从小到大检查边。加入不会形成环的边，直到选出的边足以连接所有顶点。边权相同时，可以任意选择，也可以用固定规则打破平局。
• Prim 从一个顶点开始，每次选择连接当前树与树外顶点的最小权值边。最小权值边并列时，任选一条都符合算法规则。

如果按字母顺序处理并列边，算法会依照这条规则返回一棵结果。这只是让并列选择有了确定顺序，不能据此证明图中只有这一棵 MST。

实际判断

先确认“按升序”指的是边权，而不是顶点名称或边的字母标签。对于无向连通图，所有边权互不相同足以保证 MST 唯一。权值有重复时，需要结合图的结构判断，不能只凭重复权值断定 MST 唯一或不唯一。

如果图不连通，通常求的是最小生成森林，而不是覆盖所有顶点的一棵生成树。

备注：内容仅供参考。