Union-find

---

終于抽出時間總結回顧一下Union-find了！

《算法》書中，從quick_find,quick_union到weighted_quick_union到path compression，一步步深入。下面是用C++實現的版本。

quick find

O(1)時間查找一個節點所屬的組，平均用O(n)時間合并兩個節點。思路是這樣的：將N個點所屬的組（id）初始為相應的標號：0~N-1。之后，若碰到合并兩個節點時，則將每個組內的所有點的id更新為同一個值。

#include <vector> #include <time.h> #include <fstream>using namespace std; /* O(1)查找兩個節點是否連通，O(n)時間Union 相當于給每個節點進行分組，每個組內節點的標號是一致的 */class QuickFindUF { public:QuickFindUF(int N);int get_count();int find(int p);bool connected(int p, int q);void Union(int p, int q);private:vector<int> id;int count; //連通分量數 };QuickFindUF::QuickFindUF(int N) {count = N;id = vector<int>(N);for (int i = 0; i < N; i++){id[i] = i;} }int QuickFindUF::get_count() {return count; }int QuickFindUF::find(int p) {return id[p]; }bool QuickFindUF::connected(int p, int q) {return find(p) == find(q); }void QuickFindUF::Union(int p, int q) {int pID = find(p);int qID = find(q);//先檢查是否連通。所以當需要連接兩個點時，不需要在外面檢測是否連通if (pID == qID)return;int sz = id.size();for (int i = 0; i < sz; i++){if (find(i) == pID)id[i] = qID;}count--; }//0.01s int main() {ifstream cin("mediumUF.txt");ofstream cout("outmediumUF.txt");int N;cin >> N;QuickFindUF qfUF(N);clock_t start, end;start = clock();while (cin){int p, q;cin >> p >> q;if (qfUF.connected(p, q)) continue;qfUF.Union(p,q);}end = clock();double totoal_time = (double)(end-start)/CLK_TCK;cout << qfUF.get_count() << endl;cout << "quick find total time: " << totoal_time << "s";cin.close();cout.close(); }

quick union

quick union為了提高union的速度，改變了union策略。對于每個點而言，存放它的父結點。初始時，每個點的父節點是本身。當合并兩個節點的時候，先找出這個點的祖先節點rootP,rootQ，若兩者不等，則將rootP的父節點設置成rootQ。所以，parent數組里保存的是每個點的父節點，而當一個節點的父節點是自身的時候，那么這個節點即是根節點。對于查找一個節點的父節點，時間復雜度為樹的高度；而union兩個節點的復雜度也是樹的高度，因為union的時候，需要先找出p,q兩個節點的根節點。union之后，原來以rootP為根結點的樹直接掛到rootQ上，因此所有節點的高度加1。

#include <vector> #include <fstream> #include <time.h>using namespace std;/* parent[]數組用父鏈接的形式組成了一個森林。 */class QuickUnionUF { public:QuickUnionUF(int N);int get_count();int find(int p);bool connected(int p, int q);void Union(int p, int q);private:vector<int> parent;int count;};QuickUnionUF::QuickUnionUF(int N) {parent = vector<int>(N);count = N;for (int i = 0; i < N; i++){parent[i] = i;} }int QuickUnionUF::get_count() {return count; }int QuickUnionUF::find(int p) {while (p != parent[p]){p = parent[p];}return p; }bool QuickUnionUF::connected(int p, int q) {return find(p) == find(q); }void QuickUnionUF::Union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ)return;parent[rootP] = rootQ; //以rootP為根的樹的高度加1.count--; }//0.051s int main() {ifstream cin("mediumUF.txt");ofstream cout("outmediumUF.txt");int N;cin >> N;QuickUnionUF quUF(N);clock_t start, end;start = clock();while (cin){int p, q;cin >> p >> q;if (quUF.connected(p, q)) continue;quUF.Union(p,q);}end = clock();double totoal_time = (double)(end-start)/CLK_TCK;cout << quUF.get_count() << endl;cout << "quick union total time: " << totoal_time << "s";cin.close();cout.close(); }

weighted quick union

quick union算法有一點不好的是，parent數組表示的樹可能非常不平衡。因此提出一種改進的算法。改進的地方在于：每次union的時候，不是盲目地直接將rootP的父節點設置成rootQ，而是根據兩棵樹的大小：樹小的連接到樹大的根結點上。這樣，樹就會一直保持平衡。要實現這一點，要添加一個變量來保持樹的大小。

#include <vector> #include <iostream> #include <fstream> #include <time.h>using namespace std;/* 使得樹更平衡，查找次數減少 */class WeightedQuickUnion { public:WeightedQuickUnion(int N);int get_count();int find(int p);bool connected(int p, int q);void Union(int p, int q);private:vector<int> parent;vector<int> size;int count; };WeightedQuickUnion::WeightedQuickUnion(int N) {parent = vector<int>(N);size = vector<int>(N);count = N;for (int i = 0; i < N; i++){parent[i] = i;size[i] = 1;} }int WeightedQuickUnion::get_count() {return count; }int WeightedQuickUnion::find(int p) {while (p != parent[p]){parent[p] = parent[parent[p]]; //path compressionp = parent[p];}return p; }bool WeightedQuickUnion::connected(int p, int q) {return find(p) == find(q); }void WeightedQuickUnion::Union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ) //必須加上。如果p,q本來相連，后面的代碼不能執行.return;if (size[rootP] < size[rootQ]){parent[rootP] = rootQ;size[rootQ] += size[rootP];}else{parent[rootQ] = rootP;size[rootP] += size[rootQ];}count--; }

path compression

實現了樹的平衡還沒完，還可以在查找一個節點的根結點的過程中，進一步減小樹的深度。即把樹flatten。理想情況下，只有一個根結點，所有的孩子在高度為1的地方，這樣find起來就會比較快。可以用two-pass來完成，即找到p的根結點后，把路徑上的點的根結點都設為根結點。

但是我們最后采用了一個簡便的方法：如果一個節點p的父節點parent[p] ！= p，即p不是根結點，那么就把p的父節點設置成p的爺爺節點。只需要在find的while循環中加一行代碼就可以實現了。代碼見weighted quick union代碼中注釋為//path compression的地方。達到的效果是把樹的高度減半。

總結

以上是生活随笔為你收集整理的Union-find的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。