如何動態查找連接組件

Question

使用不相交集的數據結構可以很容易地獲取Graph的連通組件。而且，它只支持Incremental Connected Components。

然而，在我的情況下，刪除邊是很常見的，這樣我在尋找一種算法或新的結構可以保持連接的組件完全動態（包括添加和刪除邊）

感謝

Answer 1

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頁，但不要（太）害怕 - 本文描述了一系列新算法動態圖（也就是說，可以有效修改的圖時間）的連通性是最簡單的。