Prim 算法和 Kruskal 算法都生成最小生成树。根据 cut 属性，这些算法的树的总成本将是相同的，但是考虑到我们在面临多个选择时按字母顺序选择它，这两种算法是否有可能以相同的总成本给出不同的 MST .例如，我们比较 max(source,dest)，对于边 A->B 和 B->C，我们比较 A 中的 A->B 和 B 中的 B->C。
谢谢
最佳答案
假设您的比较器处理两条边的成本相等并且具有相同的 max(source, dest) 字符的情况，它永远不会声明任何两条边相等。对于存在多个 MST 的可能性，图中至少有两条边必须相等。因此，MST 是唯一的，Prim 和 Kruskal 算法将返回相同的结果。
另一方面，如果您的比较器声明边 A->B(成本 1)和 A->C(成本 1)相等，则算法可能会生成不同的 MST，具体取决于它们首先考虑的边(A->B 或 A->C)。
关于minimum-spanning-tree - Prim 和 Kruskal 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13314796/