Linux 中的並查集¶
- 日期:
2024 年 6 月 21 日
- 作者:
Xavier <xavier_qy@163.com>
什麼是並查集，它有什麼用？¶
並查集是一種用於處理不相交集合的合併和查詢的資料結構。並查集支援的主要操作有：
- 初始化：將每個元素重置為一個獨立的集合，其中
每個集合的初始父節點指向自身。
- 查詢：確定特定元素屬於哪個集合，通常透過
返回該集合的“代表元素”來完成。此操作用於檢查兩個元素是否在同一集合中。
合併：將兩個集合合併為一個。
作為一種用於維護集合（組）的資料結構，並查集常用於解決離線查詢、動態連通性和圖論相關的問題。它也是 Kruskal 演算法計算最小生成樹的關鍵組成部分，這在網路路由等場景中至關重要。因此，並查集被廣泛引用。此外，並查集還在符號計算、暫存器分配等方面有應用。
空間複雜度：O(n)，其中 n 是節點數量。
時間複雜度：使用路徑壓縮可以降低查詢操作的時間複雜度，而使用按秩合併可以降低合併操作的時間複雜度。這些最佳化將每次查詢和合並操作的平均時間複雜度降低到 O(α(n))，其中 α(n) 是反阿克曼函式。在實際應用中，這大致可以被視為常數時間複雜度。
本文件介紹 Linux 並查集實現的使用。有關並查集性質和實現的更多資訊，請參閱：
Linux 並查集實現¶
Linux 的並查集實現位於檔案“lib/union_find.c”中。要使用它，請“#include <linux/union_find.h>”。
並查集資料結構定義如下：
struct uf_node {
struct uf_node *parent;
unsigned int rank;
};
在此結構中，`parent` 指向當前節點的父節點。`rank` 欄位表示當前樹的高度。在合併操作期間，秩較小的樹會連線到秩較大的樹下面，以保持平衡。
初始化並查集¶
您可以使用靜態或初始化介面完成初始化。將父指標初始化為指向自身，並設定秩為 0。示例：
struct uf_node my_node = UF_INIT_NODE(my_node);
或
uf_node_init(&my_node);
查詢並查集的根節點¶
此操作主要用於判斷並查集中兩個節點是否屬於同一集合。如果它們具有相同的根，則它們在同一集合中。在查詢操作期間，會執行路徑壓縮以提高後續查詢操作的效率。示例：
int connected;
struct uf_node *root1 = uf_find(&node_1);
struct uf_node *root2 = uf_find(&node_2);
if (root1 == root2)
connected = 1;
else
connected = 0;
合併並查集中的兩個集合¶
要在並查集中合併兩個集合，首先找到它們各自的根節點，然後根據根節點的秩將較小的節點連線到較大的節點。示例：
uf_union(&node_1, &node_2);