algorithm - 如何仅遍历图中的一个循环？

我正在 MST 上的 CLRS 中尝试 ch23，这是一个问题：

给定图 G 和最小生成树 T ，假设我们减少不在 T 中的边之一的权重。给出在修改后的图中找到最小生成树的算法。

我找到的一个解决方案是在中添加这个新的更改边T，然后在 T 中创建一个简单的循环，遍历这个循环并删除这个循环中的最大权重边，瞧，找到了新的更新 MST！

我的问题是，我如何只遍历这个简单循环上的节点？因为如果我T从这个新添加的边 in 的一个端点开始遍历，DFS/BFS 遍历可能会退出循环T。

我能想到的一种解决方案是biconnected components在T添加新边缘后找到。只会BCC找到一个，就是这个新形成的简单循环，然后我可以在我的 DFS 代码中设置一个特殊条件，说只遍历这个 BCC 中的边/节点，一旦找到后边，停止遍历.

编辑：图 G 是连接的和无向的顺便说一句

标签： algorithmgraph-theorygraph-algorithmdepth-first-searchbreadth-first-search

你的解决方案基本上是好的。为了使其更正式，您可以使用Tarjan 的寻桥算法

该算法在线性时间内找到图中的切边（又名桥）。考虑E'为切边集。很容易证明每条边都不在圆上E'。所以，都必须是图中的循环。E / E'

E您可以使用 hash-map 或数组构建函数来查找您和cut-edges集合之间的差异

从这里您可以运行简单的 for 循环来查找要删除的最大权重边缘。

希望有帮助！