算法/圖表：維護集合

Question

在應用程序中，我逐一讀取無向圖的頂點，僅當兩個頂點出現時邊纔會變得明顯。

解析後，我需要快速迭代一個接一個的圖的連接組件。我的算法選擇在解析時間建立連接組件？ （在解析時間，因爲列出邊緣相當昂貴）。

我有250個頂點，很難說出每個頂點的邊數，但假設它受限於100（也就是說，我們有250×100/2 = 12500條邊）。我也想知道一個較低的邊緣數量（比方說500）會如何影響算法的選擇。 （是的，250個頂點並不多，但在這個應用程序中，即使是小的加速計數 - 算法也會運行很多次）。

Answer 1

我想到的最簡單的解決方案是一些增強的「聯合查找」算法。 有關基礎知識，請參閱wiki article，或者由ROBERT SEDGEWICK在最新Coursera課程「算法，第1部分」中提供 - 它是在「第1周：聯合查找」期間發佈的。請查看課程archive（您可以免費註冊）。 在第1周的第45張幻燈片中，您將總結該算法的基本版本和增強版本的最壞情況時間。