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

Question

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

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

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

非常感谢！托默。

Answer 1

您可以证明它是否具有唯一的 MST 在O(E log(V)).

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

回到你原来的树，用数字对替换所有的权重，原来的权重，然后是 0 或 1，取决于它是否在你找到的 MST 中。这些数字对可以成对相加，也可以成对比较——就像正常数字一样。

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