如何遍历图中的一个循环？
How to traverse on only a cycle in a graph?
我正在尝试在 MST 的 CLRS 中使用 ch23，这里有一个问题：
Given a graph G and a minimum spanning tree T , suppose that we decrease the weight of one of the edges not in T . Give an algorithm for finding the minimum spanning tree in the modified graph.
我找到的一个解决方案是在T中添加这个新的变化边，然后在T中创建一个简单的循环，遍历这个循环并删除这个循环中的最大权重边，瞧，新更新的MST找到了！
我的问题是，如何只遍历这个简单循环上的节点？因为 DFS/BFS 遍历可能会超出循环，如果我，比如说，从 T 中新添加的边的一个端点开始遍历 T。
我能想到的一个解决方案是在添加新边后在T中找到biconnected components。只会找到一个BCC，就是这个新形成的simple-cycle，那么我可以在我的DFS代码中加入一个特殊条件，说在这个BCC中只遍历edges/nodes，并且一次回找到边，停止遍历。
编辑：顺便说一句，图 G 是连通且无向的
你的方案基本上是好的。为了使其更正式，您可以使用 Tarjan's bridge-finding algorithm
该算法在线性时间内找到图中的切边（也称为桥）。将 E' 视为切边集。很容易证明E'中的每条边都不在圆上。所以，E / E' 一定是图中的循环。
您可以使用散列映射或数组构建函数找出您的 E 和 cut-edges 集
之间的区别
从这里您可以运行 简单的 for 循环来找到您要删除的最大权重边。
希望有所帮助！
我正在尝试在 MST 的 CLRS 中使用 ch23，这里有一个问题：
Given a graph G and a minimum spanning tree T , suppose that we decrease the weight of one of the edges not in T . Give an algorithm for finding the minimum spanning tree in the modified graph.
我找到的一个解决方案是在T中添加这个新的变化边，然后在T中创建一个简单的循环，遍历这个循环并删除这个循环中的最大权重边，瞧，新更新的MST找到了！
我的问题是，如何只遍历这个简单循环上的节点？因为 DFS/BFS 遍历可能会超出循环，如果我，比如说，从 T 中新添加的边的一个端点开始遍历 T。
我能想到的一个解决方案是在添加新边后在T中找到biconnected components。只会找到一个BCC，就是这个新形成的simple-cycle，那么我可以在我的DFS代码中加入一个特殊条件，说在这个BCC中只遍历edges/nodes，并且一次回找到边，停止遍历。
编辑：顺便说一句，图 G 是连通且无向的
你的方案基本上是好的。为了使其更正式，您可以使用 Tarjan's bridge-finding algorithm
该算法在线性时间内找到图中的切边（也称为桥）。将 E' 视为切边集。很容易证明E'中的每条边都不在圆上。所以，E / E' 一定是图中的循环。
您可以使用散列映射或数组构建函数找出您的 E 和 cut-edges 集
从这里您可以运行 简单的 for 循环来找到您要删除的最大权重边。
希望有所帮助！