algorithm - 确定给定的加权图是否具有唯一的 MST

Question

我正在寻找一种算法(或任何其他方式)来确定给定的加权图是否在 O(ElogV) 中具有唯一的 MST(最小生成树)？

我对权重一无所知(例如 weight(e1) != weight(e2))，如果此图只有一个唯一的 MST，则算法只返回 True，否则返回 False。

我开始使用 Kruskal 的算法，并检查 find-set(u)==find-set(v) 是否在 MST 中有一个圆圈，但这种方式并没有涵盖我认为的所有场景:(

非常感谢!托默。

Answer 1

你可以在O(E log(V))中证明它是否有唯一的MST。

首先用标准技术找到最小生成树。

回到原来的树，将所有权重替换为数字对、原始权重，然后根据它是否在你找到的 MST 中替换为 0 或 1。这些数字对可以成对相加，也可以成对比较 - 就像普通数字一样。

现在使用标准技术找到具有这些有趣权重的最小生成树。您找到的 MST 将是与原始树共享 最少 边的 MST。因此，如果有多个 MST，您一定会找到一个不同的 MST。