图有两个/三个不同的最小生成树？

Question

我试图找到一种检测给定图G是否具有两个不同的最小生成树的有效方法.我也试图找到一种方法来检查它是否有3种不同的最小生成树.我现在的天真解决方案是运行Kruskal算法一次并找到最小生成树的总重量.稍后,从图中移除边缘并再次运行Kruskal算法,并检查新树的权重是否是原始最小生成树的权重,对于图中的每个边都是如此.运行时是O(| V || E | log | V |),这根本不是很好,我认为有更好的方法.

任何建议都会有所帮助,在此先感谢

Answer 1

假设您有一个T0图的 MST。现在，如果我们可以获得另一个 MST T1，它必须至少有一条E与原始 MST 不同的边。抛弃E，T1现在图被分成两个部分。然而，在 中T0，这两个分量必须连接，因此这两个分量之间将存在另一条边，其权重与 完全相同E（或者我们可以用另一个分量替换权重较大的一个，并得到较小的 ST）。这意味着用另一个边替换E将为您提供另一个 MST。

这意味着如果有多个 MST，我们总是可以仅更改 MST 的一条边并获得另一个 MST。因此，如果您正在检查每条边，请尝试用具有相同权重的边替换该边，如果您得到另一个 ST，它是 MST，您将获得更快的算法。