1

这是一个家庭作业问题。我不想要解决方案 - 我提供的是我一直在考虑的解决方案，并希望知道它是否好或为什么有缺陷。

我的动机是找出未加权、无向图的哪些边不属于任何 MST。这个问题只有在多条边具有相同值时才有意义，否则 MST 是唯一的。

我的想法来自 Prim's Algorithm 的微小变化——而不是在每一步（其中 S 和 T 是两组顶点）中添加从 S 到 T 的最小边——而是寻找相同值的最小边和更多边从 S 到最小边到达的顶点。通过这样做，（所以我想）我们将收到一个包含出现在任何 MST 中的所有边的图。如果这是正确的，我可以简单地将边缘列表与原始图形边缘列表进行异或，以找出任何 MST 中没有的边缘。

提前致谢。

4

1 回答 1

1

您是否添加了所有找到的边缘（=那些具有相同权重的边缘）？如果是这样，您将失去一些优势：

考虑一个边成本相等的五边形。您从 1 个节点开始，将 2 条边添加到 2 个相邻节点。在下一步中，您将添加从这 2 个相邻节点到 2 个断开连接的节点的 2 条边，您就完成了。但是，所有边的成本都相同，并且它们都有效地存在于 MST 中。最后 2 个节点之间的边不包含在您的算法中，但可能是 MST 的一部分。

情况更糟。假设最后一条边的成本较低。您的算法仍然不包括它，但它存在于每个 MST 中。您在每个步骤中添加多个边以考虑所有可能性，但添加这些边会更改后续步骤。

于 2012-12-11T08:05:22.257 回答