因此，确定一条边是否在最小生成树中似乎可以归结为该边是否是某个循环中最重的边的问题。我知道如何使用 DFS 检测边缘是否在循环中，但是如何确定它是否是该循环中最重的边缘？是通过找到循环并选择其中最重的边缘吗？
最佳答案
假设所有的边都有不同的权重，一个简单且相当优雅的算法是做一个修改过的 DFS。请注意，如果这条边是某个循环中最重的边，那么如果您要查看通过删除所有比当前边重的边而形成的图，那么从边的端点返回到该边的开头必须有一些路径边，因为这条路径与边本身相结合，形成了一个循环，其中给定的边是最重的边。相反，如果没有包含给定边最重的边的循环，那么如果您要在此图中从边的末端返回源头进行搜索，则将无法返回到边缘的源头，否则您可以将其完成为一个循环。这给出了以下简单的算法:在原始图中从边的端点返回到源执行 DFS，但是每当遇到比原始边重的边时，不要处理它(这模拟从图)。如果您的 DFS 将您从边缘的末端带回源头，那么您知道必须存在某个循环，其中边缘是最重的边缘，如果没有这样的循环，那么您将无法获得回到边缘的源头。
在边缘不明显的情况下，您将执行与上述相同的搜索，但您将删除权重大于或等于当前边缘权重的所有边缘。这样做的原因是，如果在这个变换后的图中有一条从边的末端到边的起点的路径，你知道我们最终没有使用任何与原始边，因此找到的任何路径都可以完成为给定边最重的循环。如果没有路径，那么要么
无论哪种情况，它都不是周期中最重的边缘。
该算法的运行时间为 O(m + n)，即执行标准 DFS 所需的时间。
希望这可以帮助!
关于algorithm - 检测边缘是否是循环中最重的边缘，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9550320/