algorithm - 检测一条边是否是循环中最重的边

Question

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

Answer 1

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

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

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

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

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

希望这对您有所帮助!