如何动态地发现连接的设备 [英] how to find Connected Component dynamically

问题描述

使用不相交集数据结构可以很容易地得到图的连通分量。而且，它只是支持增量连接组件的。

Using disjoint-set data structure can easily get connected component of Graph. And, it just supports Incremental Connected Components.

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

However, in my case, removing edge is very common so that I am looking for an algorithm or new structure can maintain Connected Components fully dynamically(including adding and removing edge)

感谢

推荐答案

的聚对数确定性完全动态算法的连接，最小生成树，2边，和biconnectivity（霍尔姆，德利希滕贝格和2001年Thorup）给出了一个算法，允许任意序列的边缘插入，删除和连接的查询，以更新（插入和删除）以O（日志（N）^ 2）进行摊销，并查询取O（日志（N）/日志（日志（N）））时间，其中n是图中的顶点的数目。这些时间界限假设图开始没有边。

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001) gives an algorithm that allows an arbitrary sequence of edge insertions, deletions and connectivity queries, with updates (insertions and deletions) taking O(log(n)^2) amortised time, and queries taking O(log(n)/log(log(n))) time, with n being the number of vertices in the graph. These time bounds assume that the graph starts with no edges.

我只脱脂第2的38页，但不要（太）吓坏了 - 本文描述了的动态图形的（即，图表，能够一堆新算法可以有效地改性随时间），其中的连接是最简单的。

I only skimmed the first 2 of its 38 pages, but don't be (too) scared -- the paper describes a bunch of new algorithms on dynamic graphs (that is, graphs that can be efficiently modified over time) of which connectivity is the simplest.

这篇关于如何动态地发现连接的设备的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！