使用不相交集数据结构可以很容易地得到图的连通分量。而且，它只是支持增量连接组件 http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/incremental_components.html.
然而，就我而言，删除边缘很常见，因此我正在寻找一种算法或新结构可以维护连通分量完全动态地（包括添加和删除边缘）
给出一种算法，允许任意序列的边插入、删除和连接查询，更新（插入和删除）需要 O(log(n)^2) 摊销时间，查询需要 O(log(n)/log(log (n))) 时间，其中 n 是图中的顶点数。这些时间界限假设图开始时没有边。
我只浏览了 38 页中的前 2 页，但不要（太）害怕——这篇论文描述了一堆新算法动态图（即可以随着时间的推移有效修改的图表）其中连接性是最简单的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
