c++ - 删除边后保留图连通分量数的动态图算法的实现

Question

我有一个图表，我想为它获取连通分量的数量。这可以通过 BFS 或 DFS 遍历轻松完成。但之后，我将迭代地删除图形的一些边，并再次询问生成的图形中连通分量的数量。

一个简化的使用示例是:

graph G = some_graph();
while (some_condition) {
    cout << connected_components(G);
    edge e = some_edge_of(G);
    G.delete(e);
}

我已经找到了几个处理这个主题的动态图算法(使用数据结构允许比再次遍历图更快地重新计算连接组件的数量)。

但是你能帮我节省一些实现它们的时间并提供一些免费实现的链接吗？ (最好使用 C 或 C++)

Answer 1

Boost Graph Library有你要找的东西， 尽管从我的角度来看，学习曲线非常陡峭......

有a book关于它。