确定给定的加权图是否有唯一的最小生成树。

Question

9

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

我不知道权重的情况（例如weight（e1）！= weight（e2）），并且该算法仅在此图仅具有一个唯一的MST时返回True，否则返回False。

我开始使用Kruskal算法，并检查find-set（u）== find-set（v）以便在MST中出现圆形，但是这种方法并没有涵盖我想到的所有情况:(

非常感谢！ Tomer.

- TomerGod

我不是MST专家，但我认为你不能在O（ElogV）中检查它是否只有1个MST。你认为你能做到的原因是什么？ - Daniel

3

可能是与图有两个/三个不同的最小生成树？重复的问题。 - David Eisenstat

@Daniel O(ElogV) 是用于查找给定图的最小生成树的 Kruskal 算法 / Prim 算法的时间复杂度，因此解决方案必须是这些算法的变体... - TomerGod

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

您可以在O(E log(V))的时间复杂度内证明它是否具有唯一的最小生成树。

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

返回到原始树，用数字对替换所有权重，第一个数字是原来的权重，第二个数字是0或1，基于它是否在您找到的最小生成树中。这些数字对可以成对相加，也可以像普通数字一样成对比较。

现在使用这些奇怪的权重找到一个最小生成树的标准技术。您找到的MST将是与原始树共享最少的边的MST。因此，如果存在多个MST，则保证会找到另一个不同的MST。