如何检测无向图中的圈并丢弃该圈中权重最大的边？

Question

我知道DFS或union-find可以用来检测循环。但是，有没有一种快速的方法可以在这个循环中找到权重最大的边呢？

Answer 1

不，DFS和顺序搜索是最佳解决方案。只需找到周期，并通过其边缘找到最大权重的边缘。复杂性在这里并不重要--不管怎样，你必须找到循环，找到最大边的复杂性是相同的。

Answer 2

没有好的方法可以只做一次，但是如果你要迭代直到图是非循环的，你会留下一个最小生成树，它可以在线性时间内计算。