Prim 和 Kruskal 的算法都产生最小生成树。根据割属性，对于这些算法，树的总成本将是相同的，但是这两种算法是否有可能以相同的总成本给出不同的 MST，因为我们在面临多个选择时按字母顺序选择它. 例如，我们比较 max(source,dest)，对于边 A->B 和 B->C，我们比较 A->B 中的 A 和 B->C 中的 B。
谢谢
问问题
13130 次
2 回答
6
假设您的比较器处理两条边的成本相等并且具有相同的 max(source, dest) 字符的情况，它永远不会声明任何两条边相等。为了存在多个 MST 的可能性，图中至少两条边必须相等。因此，MST 是唯一的，Prim 和 Kruskal 的算法都将返回相同的结果。
另一方面，如果您的比较器声明边缘 A->B（成本 1）和 A->C（成本 1）相等，则算法可能会生成不同的 MST，具体取决于它们首先考虑的边缘（A->B 或 A->C）。
于 2012-11-13T02:43:15.687 回答
0
一个图肯定有可能有多个 MST，只要这些 MST 的不同表示具有相同的总权重。否则，总重量较低的将是真正的 MST，而另一个将不再是 MST。
由于 Prim 和 Kruskal 的算法有不同的步骤，因此在实际遍历过程中，它们可能会选择相同权重的不同边，但仍以相同的总权重结束。
但是，如果您添加您在问题中陈述的限制（选择字母表中第一个节点），Prim 和 Kruskal 的 MST 应该是相同的树，对于每个决策，即使它们是相同的权重，更喜欢 Kruskal 和 Prim 的相同优势。
于 2019-11-09T18:17:11.930 回答