今天主要介紹的是并查集這種數據結構。

其本質上是解決某一些特定問題的而設計出的數據結構。大家可以了解下這種數據結構，作為自己知識的儲備。

  假設有 n 個村莊，有些村莊之間有連接的路，有些村莊之間并沒有連接的路

設計一個數據結構，能夠快速執行 2 個操作：

1. 查詢 2 個村莊之間是否有連接的路
2. 連接 2 個村莊

  如果使用數組、鍊表、平衡二叉樹、集合(Set) 都可以完成需求，但是查詢、連接的時間複雜度都是 O(n)。  并查集能做到查詢、連接的均攤時間複雜度都是 O(α(n))，α(n) < 5，非常适合解決這類“連接”相關的問題。

并查集也叫作不相交集合（Disjoint Set）

并查集有2個核心操作:

• 查找（Find）：查找元素所在的集合(這裡的集合并不是特指Set這種數據結構，是指廣義的數據集合)
• 合并（Union）：将兩個元素所在的集合合并為一個集合

有 2 種常見的實現思路：

• Quick Find查找（Find）的時間複雜度：O(1)合并（Union）的時間複雜度：O(n)
• Quick Union查找（Find）的時間複雜度：O(logn), 可以優化至 O(()), α() < 5合并（Union）的時間複雜度：O(logn), 可以優化至 O(()), α() < 5

假設并查集處理的數據都是整型，那麼可以用整型數組來存儲數據。

• 數組索引代表元素值
• 索引對應的值代表這個元素的根節點

将｛0，1，2，3，4，5，6，7｝存儲到數組中，如下圖：

  因此，并查集是可以用數組實現的樹形結構（二叉堆、優先級隊列也是可以用數組實現的樹形結構）

/** * 查找v所屬的集合(根結點) */ public abstract int find(int v); /** * 合并v1、v2所在的集合 */ public abstract void union(int v1, int v2); /** * 檢查v1、v2是否屬于同一集合 */ public boolean isSame(int v1, int v2);

isSame()的實現十分簡單

public boolean isSame(int v1, int v2){ return find(v1) == find(v2); }

初始化時，每個元素各自屬于一個單元素集合

private int[] parents; public UnionFind(int capacity){ if(capacity < 0){ throw new IllegalArgumentException("capacity must >= 1"); } parents = new int[capacity]; for (int i = 0; i < parents.length; i ) { parents[i] = i; } }

  Quick Find 的 union(v1, v2)讓 v1 所在集合的所有元素都指向 v2 的根節點。并且 Quick Find 的高度永遠保持 <= 2。

例如：  将｛0，1，2，3，4，5｝初始化為并查集，每個元素各自屬于一個單元素集合：{0}, {1}, {2}, {3}, {4} 。

合并 1 和 0，union(1, 0)，即 {1} 指向了 {2} 。

然後，合并 1 和 2，union(1, 2)，1 所在集合有 {0, 1}，即 {0, 1} 指向了 2 。

再合并 3 和 4，union(3, 4)，即 {3} 指向了 {4} 。

合并 0 和 3，union(0, 3)，0 所在集合為 {0, 1, 2}，3 所在集合為 {3,4}，如下：

/** * 将v1所在集合的所有元素都嫁接到v2的父節點上 * v1 v2 union(v1,v2) * 0 4 4 * 1 2 3 0 1 2 3 */ public void union(int v1, int v2){ int p1 = parents[v1]; int p2 = parents[v2]; for (int i = 0; i < parents.length; i ) { if(parents[i] == p1){ parents[i] = p2; } } }

  Quick Find 查找的時候，由于數組中存儲的就是根結點，因此直接取出即可。

對上圖執行 find(): find(0) == 2 find(1) == 2 find(2) == 2 find(3) == 4

/** * 父節點就是根節點 */ public int find(int v){ rangeCheck(v); return parents[v]; }

  今天主要介紹了并查集這種數據結構，然後詳細的講述了Quick Find的實現思路。希望給大家的知識庫增加一些新的知識儲備。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!