如何动态查找连通组件

Question

16

使用不相交集数据结构可以轻松获取图的连通分量。而且，它仅支持增量连通组件。

然而，在我的情况下，删除边缘非常普遍，因此我正在寻找一种算法或新的结构，可以完全动态地维护连接组件（包括添加和删除边缘）

- Chang

维基百科文章中有一个参考文献。 - n. m.

@ n.m. 哪一个？“对数空间中的无向连通性”？ - Chang

"一个在线的边缘删除问题" - n. m.

@n.m.：这个时间复杂度只适用于森林，而不是一般图，在每次边删除时仍然有O(n)的时间复杂度。 - templatetypedef

@n.m.：不幸的是，该算法仅处理边缘删除，而不是插入和删除。 - j_random_hacker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

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页中的前两页，但不要太害怕——本文描述了一堆关于动态图的新算法（即可以有效修改的图），其中连通性最简单。