4

因此，似乎确定一条边是否在最小生成树中可以归结为该边是否是某个循环中最重的边的问题。我知道如何使用 DFS 检测边缘是否处于循环中，但如何确定它是否是该循环中最重的边缘？是通过找到循环并选择其中最重的边缘吗？

4

1 回答 1

6

假设所有的边都有不同的权重，一个简单而相当优雅的算法就是做一个修改后的 DFS。请注意，如果这条边是某个循环中最重的边，那么如果您要查看通过删除所有比当前边重的边所形成的图，那么从边的端点到边的起点必须有一些路径边，因为这条路径与边本身相结合，形成了一个循环，其中给定的边是最重的边。相反，如果没有包含给定边最重的边的循环，那么如果您要在此图中从边的末端到源进行搜索，您将无法返回到边缘的源头，否则您可以将其完成为一个循环。这给出了以下简单的算法：在原始图中从边缘的端点返回源进行 DFS，但是每当遇到比原始边缘重的边缘时，不要处理它（这模拟从图中删除它）。如果您的 DFS 将您从边缘的末端带回源头，那么您知道必须有某个循环，其中边缘是最重的边缘，如果没有这样的循环，那么您将无法获得回到边缘的源头。

在边缘不明显的情况下，您将执行与上述相同的搜索，但您将删除权重大于或等于当前边缘权重的所有边缘。这样做的原因是，如果在这个转换后的图中有一条从边的末端到边的起点的路径，你知道我们最终没有使用任何成本与原始边缘，因此找到的任何路径都可以完成给定边缘最重的循环。如果没有路径，那么要么

  1. 每个包含给定边的循环都有一些比它重的边，或者
  2. 每个包含给定边的循环都有一些与它具有相同成本的边。

无论哪种情况，它都不是周期中最重的边缘。

该算法的运行时间为 O(m + n)，即执行标准 DFS 所需的时间。

希望这可以帮助！

于 2012-03-04T00:31:03.730 回答