可以對不相交集合執行哪些操作？

Question

我剛剛研究了不相交集數據結構，並且我知道它也被稱爲「union-find數據結構」，union和find是這個數據結構的兩個主要操作。我們可以在不相交集合上執行聯合，類似的，我們可以執行查找操作;我想知道除了union和find以外，我們可以在不相交的集合上執行哪些其他操作。

Answer 1

獨立集合結構也被稱爲「合併 - 查找結構」。因此無論如何union,find和MakeSet操作應該得到支持。其他行動不是這個結構的全部，它們是否得到支持取決於實施和目標。有時候您需要專門選擇特定的實施方式，以滿足您項目對額外操作的需求。

除此之外，如果我們支持的其他基本的設置相關的操作這將是很好。讓我們列舉一下：

• 十字路口兩套。由於集合是不相交的，除非這兩個集合重合，否則它總是空的。
• 工會的兩套 - 支持開箱即用。
• 從集合獲取元素 - 的支持，這是最有可能的find結果。
• 從集合刪除元素 - 取決於執行。當集合被實現爲森林時，它很棘手並且需要較慢的附加操作。當集合被實現爲鏈表時，它很簡單。
• 枚舉設定，即迭代在該給定組中的每個元件。這個依賴於實現：鏈接列表很簡單，對於像森林一樣的實現，它需要額外的結構來支持。

Answer 2

使用vanilla union-find數據結構，您無法枚舉實際集合，因此許多集合操作都不可用。這是因爲在香草版本中，只有指向一個方向的指針---在下圖中，每條對角線對應於向上的箭頭，並且根（頂部線）是集合的根對象：

 o [set1]   o [Set2] 
    /\    \ 
    o o    o 
/
o 

所以沒有辦法找到所有的對象，比如set 1;例如，您不能從根節點追蹤到它們的路徑。您也可以向下指針，但這會顯着地使數據結構複雜化，因爲對象在數據結構中可以有任意數量的父項。

所以它實際上多爲以下操作：

• 答到：做我的對象A和B屬於同一組或沒有？
• 合併設置S1和S2，以便在集合中的所有對象現在都被認爲屬於同一組

爲了詳細說明這一點，工會組數據結構有它支持的操作非常低的時間複雜度;合併集合和回答相同集合查詢採取分攤的恆定時間（O（1））;由於這種非常複雜的時間，你不能支持所有的設置操作。例如，一個標準集表示是由一個[二進制]搜索樹，其中大多數操作至少具有O（log n）複雜性。

Answer 3

聯合發現不相交集合結構的關鍵不在於執行基本集合操作，因爲您的問題和其他受訪者似乎暗示。相反，它是關於某些算法需要的結構的高效實現。特別是，找到連接組件和最小生成樹將在聯合查找不相交集之上構建其最有效的實現。