检测边缘是否是在一个周期内最重的边缘

Question

如此看来，在确定边缘是否处于最小生成树可以降低到的边缘是否是一些周期的最重的边缘问题。我知道如何使用DFS检测边缘是否处于循环中，但是如何确定它是否是该循环中最重的边缘？是通过找到周期并选择最重的边缘吗？

Answer 1

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

在边缘没有明显的情况下，你会做同样的搜索同上，但你会删除其重量大于或等于当前边的权重所有边缘。其原因是，如果在这个变换图中存在从边的末端到边的开始的路径，则知道事实上我们并没有最终使用具有与原始边缘，因此找到的任何路径都可以完成到给定边缘最重的周期。如果没有路径，则要么

1. 包含给定边的每个周期有一些边缘的严格比它更重，或
2. 包含给定边的每个周期有一定的优势，具有相同的成本，因为它。

在这两种情况下，它不是在循环中最重的边缘。

该算法的运行时间为O（M + N），做一个标准DFS所需的时间。

希望这会有所帮助！