如何动态查找连接组件

使用不相交集的数据结构可以很容易地获取Graph的连通组件。而且，它只支持Incremental Connected Components。如何动态查找连接组件

然而，在我的情况下，删除边是很常见的，这样我在寻找一种算法或新的结构可以保持连接的组件完全动态（包括添加和删除边）

感谢

2011-08-30 Chang

[维基百科文章]（http://en.wikipedia.org/wiki/Connected_component_（graph_theory））有一个参考。 –

@ n.m.哪一个？ “日志空间中的无向连接”？ – Chang

“在线边缘删除问题” –

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001)给出了一种算法，该算法允许任意序列的边缘插入，删除和连接性查询，其中更新（插入和删除）取O（log（n）^ 2）摊销时间，并且查询取O（log（n）/ log log（n）））时间，其中n是图中顶点的数量。这些时间限制假定图形以无边缘开始。

我只剔除了其38页中的前2页，但不要（太）害怕 - 本文描述了一系列新算法动态图（也就是说，可以有效修改的图时间）的连通性是最简单的。

2011-08-31 13:19:16

回答