我正在寻找一种算法(或任何其他方式)来确定给定的加权图是否在 O(ElogV) 中具有唯一的 MST(最小生成树)？
我对权重一无所知(例如 weight(e1) != weight(e2))，如果此图只有一个唯一的 MST，则算法只返回 True，否则返回 False。
我开始使用 Kruskal 的算法，并检查 find-set(u)==find-set(v) 是否在 MST 中有一个圆圈，但这种方式并没有涵盖我认为的所有场景:(
非常感谢! 托默。
最佳答案
你可以在O(E log(V))中证明它是否有唯一的MST。
首先用标准技术找到最小生成树。
回到原来的树，将所有权重替换为数字对、原始权重，然后根据它是否在你找到的 MST 中替换为 0 或 1。这些数字对可以成对相加，也可以成对比较 - 就像普通数字一样。
现在使用标准技术找到具有这些有趣权重的最小生成树。您找到的 MST 将是与原始树共享 最少 边的 MST。因此，如果有多个 MST，您一定会找到一个不同的 MST。
关于algorithm - 确定给定的加权图是否具有唯一的 MST，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17307893/