我正在尝试在 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 已找到!
我的问题是，如何只遍历这个简单循环上的节点？因为如果我从 T 中新添加的边的一个端点开始 T 中的遍历，那么 DFS/BFS 遍历可能会超出循环。
我能想到的一个解决方案是在添加新边后在T 中找到双连通组件。只有一个 BCC 会被发现，这是这个新形成的简单循环，然后我可以在我的 DFS 代码中加入一个特殊条件，说只遍历这个 BCC 中的边/节点，并且一次返回-找到边，停止遍历。
编辑:顺便说一句，图 G 是连通且无向的
最佳答案
你的解决方案基本上是好的。为了使其更正式，您可以使用 Tarjan's bridge-finding algorithm
该算法在线性时间内找到图中的切边(也称为桥)。将 E' 视为切边集。很容易证明E'中的每条边都不在圆上。所以，E/E' 一定是图中的循环。
您可以使用 HashMap 或数组构建函数来找出您的E 和cut-edges 集之间的差异
从这里您可以运行简单的 for 循环来找到您要删除的最大权重边。
希望对您有所帮助!
关于algorithm - 如何遍历图中的一个循环？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52904065/