c++ - 删除边并在必要时拆分连接的组件(C++、Boost)

Question

我有一个很大的图(顶点数可以在50,000-100,000之间，邻接矩阵不需要稀疏)。可以删除/添加图中的边，我想在此类更改后更新生成的连接组件结构。我自己在 C++ 中通过 BFS 搜索以一种直接的方式实现了这一点(跟踪 unordered_map 连接的组件 id 的顶点并更新它们)，但我想知道是否有更有效的方法使用 Boost 的图形库来做到这一点。

我能够在 Stackoverflow 中找到一些与此类似的问题，并开始了解 filtered_graph(和 connected_components 函数)，但我担心开销每次我们添加或删除边缘时，都会参与创建此类过滤实例。 (或者这应该是一个问题吗？!)

Answer 1

我相信您的解决方案本质上是最好的。如果只允许添加边，那么我相信可以通过根据包含的顶点跟踪连接组件来改进算法，然后当包含边时检查两个顶点是否属于不同的连接组件，在这种情况下，您合并两个连接的组件。这会将复杂性从二次方降低到每条边添加的最佳情况。但是，如果允许您插入和删除边，除了您所描述的之外，我看不到任何渐近更快的方法来解决问题。