Union Find

Photo by Anthony DELANOIX on Unsplash
Photo by Anthony DELANOIX on Unsplash
Union Find data structure 又稱 disjoint set data structure。它是一個資料結構,用來儲存一堆 disjoint set。它提供兩個操作,一個是用來合併兩個 sets,另一個是用來尋找給定元素的 set。

Union Find data structure 又稱 disjoint set data structure。它是一個資料結構,用來儲存一堆 disjoint set。它提供兩個操作,一個是用來合併兩個 sets,另一個是用來尋找給定元素的 set。

Union Find

Union Find data structure 中有一個叫 parents 的 array。它記錄著每一個元素歸屬的 set。一開始,每個元素自成一個 set。之後,透過呼叫 union() 來合併給定的兩個 sets。find() 回傳傳入元素的 set 編號。

public class UnionFind {
    private final int[] parents;

    public UnionFind(int size) {
        parents = new int[size];
        for (int i = 0; i < size; i++) {
            parents[i] = i;
        }
    }

    int find(int x) {
        while (x != parents[x]) {
            parents[x] = parents[parents[x]];
            x = parents[x];
        }
        return x;
    }

    void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);

        if (parentX < parentY) {
            parents[parentY] = parentX;
        } else if (parentX > parentY) {
            parents[parentX] = parentY;
        }
    }
}

時間與空間複雜度

在一開始初始化 parents 時,需要的時間複雜度為 O(n),其中 n 為元素數量。

Find() 需要的時間複雜度為 O(α(n)),其中 αinverse Ackermann function,它會成長非常地慢,所以可以將它視為常數時間。所以,O(α(n)) ≈ O(1)。因此,Find() 的時間複雜度為 O(1)。

Union() 使用到 Find(),所以它的時間複雜度是 O(1)。

Union Find data structure 內部需要一個 parents。所以,它的空間複雜度為 O(n)。

範例

參考

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You May Also Like
Photo by Léonard Cotte on Unsplash
Read More

Depth First Search (DFS)

深度優先搜尋(DFS)演算法是一種圖形搜尋演算法。從給定的一個點開始,它會先探索該點的一個相鄰點。再來,探索該相鄰點的一個相鄰點。這樣子一直探索下去,直到某的點沒有相鄰點時,它就會退回到上一個點,並探索該點的下一個相鄰點。它會一直這樣地探索下去,直到找到結果,或是探索完所有的點。
Read More
Photo by Pedro Lastra on Unsplash
Read More

Breadth First Search (BFS)

廣度優先搜尋(BFS)演算法是一種圖形搜尋演算法。從給定的一個點開始,它會先探索該點所有的相鄰點。再來,依序探索這些相鄰點的相鄰點。這樣子一層一層地探索下去,直到找到結果,或是探索完所有的點。
Read More
Photo by Simon Hermans on Unsplash
Read More

Priority Queue & Heap

Priority queue 是一個很好用的 data structure。它可以在常數時間內提供最大或最小值。在了解它之前,我們要先了解另一個 data structure 叫 heap。因為 priority queue 常常會用 heap 來實作。
Read More
Photo by Folco Masi on Unsplash
Read More

Binary Search Tree

二元搜尋樹(Binary search tree, BST)是一種二元樹(binary tree)。它提供了一些有用操作,包含 search、insert、delete、minimum、maximum、successor 和 predecessor。
Read More