我正在尝试在MST的CLRS中使用ch23，这是一个问题：
给定一个图G和最小生成树T，假设我们减少了不在T中的边之一的权重。给出一种用于在修改后的图中找到最小生成树的算法。
我发现的一个解决方案是在中添加新的更改边T，然后在T中创建一个简单的循环，遍历该循环并删除此循环中的最大权重边voila，找到新的更新的MST！
我的问题是，如何只遍历此简单循环上的节点？因为如果我说T从该新添加的边沿的一个端点开始遍历，则DFS / BFS遍历可能会超出周期T。
我想到的一种解决方案是在添加新优势之后找到biconnected componentsin T。只会BCC找到一个，这是这个新形成的简单循环，然后我可以在DFS代码中放入特殊条件，说仅遍历此BCC中的边/节点，一旦找到后边，就停止遍历。
编辑：图G已连接并且是无向的
您的解决方案基本上是好的。为了使其更加正式，您可以使用Tarjan的桥接查找算法
该算法以线性时间在图形中找到最前沿（也称为桥）。考虑E'是最前沿的。这是很容易证明，在每边E'可以不上一圈。因此，E / E'必须是图中的循环。
您可以使用哈希映射或数组构建函数来查找您E的cut-edges集合与集合之间的差异
在这里，您可以运行简单的for循环来找到要删除的最大重量边。
希望对您有所帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句