我有一个最小生成树。我给它加了一个优势。肯定形成了一个循环。我需要找到属于该循环的所有边缘，即所有后边缘。这能多快完成？我的解决方案- 例如，如果它是边 (1,4)，则在所有位置将 4 添加到 Adj(1) 并每次运行 dfs。例如。如果 Adj(1) 有 2,3,5，先在 2 之前加 4，运行 DFS。我会得到一个后缘。然后在 2 和 3 之间添加 4 并运行 dfs。我得到另一个后缘。然后在 3 到 5 之间，依此类推。有没有更快的方法来做到这一点？
最佳答案
在树中，任何一对顶点之间都有一条(简单的)路径。如果要添加边 (i,j)，首先在树中找到 i 和 j 之间的路径，然后您将得到循环 - 它由该路径中的所有顶点组成(并转弯添加 (i,j) 作为边后进入循环。
关于c++ - 有什么方法可以在无向/有向图中快速找到属于循环(后边)的所有边？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20471502/