Algorithm(4th) 1.5 union-find演算法

• 2021 年 5 月 2 日
• 筆記

問題描述

問題輸入是一對整數對，每個整數都代表一個對象，一對整數」p,q「表示 」p與q相連「（具有自反性，傳遞性，對稱性，被歸到一個等價類里），要求編寫程式來篩除在輸入時就已經在一個等價類里的整數對。這個演算法可以在電腦網路連結方面發揮作用：每個整數相當於電腦，整數對相當於網路間的連結，我們的程式可以判斷為了使p，q兩個電腦連結，需不需要添加一個新的線路。

具體思想

1.根節點判斷

我們可以通過一個「概念上」的森林來實現我們的程式。我們把union-find演算法打包成一個類，在其中設置一個名為id的數組用來存放每個節點的下一個連結對象，這樣可以通過接受一個數組的秩來不斷訪問它所連結的下一個對象，直至到一個秩和所存儲對象節點號相同的節點（根節點）。而比較兩個節點的根節點就可以判斷他們是否連在同一個根節點上，進而判斷出兩個節點是否已經連結。

2.加權連結

如果判斷兩個節點沒有連結到一個根節點，我們就對他們的根節點進行連結。這時就會產生一個問題：p去連q還是q去連p。這裡我們採用加權的演算法：引入一個數組sz（size）來記錄每個節點作為根節點時樹中的節點數，把它作為節點的權值。每次進行根節點連結時，我們總是把權值小的根節點連結到權值大的根節點上。這樣的好處是可以極大地降低樹的高度的增加速度（最大程度降速的方式是把樹高度作為權值的加權連結，但經過路徑壓縮後，這種方式變得沒有必要），從而降低查找根節點時的時間量級。在最壞的情況下，要連結的樹的大小總是相等的，且都是2的冪，則把所有的N個節點合成一個樹，這個樹的高度是底數為2的N的對數。
致使查找要檢索的高度也達到O(logN)。

PS:本圖取自Algorithm(4th)中譯版P146（原版P229）

實現程式碼

#include<iostream>
#include<vector>
#include<random>

using namespace std;

//WeightedQuickUnion(加權快速連結)
class WQU {
	vector<int> id;
	vector<int> sz;
	int count = 0;
	int numberOfSite = 0;
public:
	int find(int p);
	void Union(int p, int q);
	int get_count() { return count; }
	bool connected(int p, int q); 
	int Count(int n);
	int newSite();
};

bool WQU::connected(int p, int q) {
	if (p >= numberOfSite || q >= numberOfSite) {
		throw runtime_error("Site does not exist");
	}
	return find(p) == find(q);
}

//壓縮路徑find，遞歸，只修改查找時經歷節點的連結
int WQU::find(int p) {
	if (p >= numberOfSite) {
		throw runtime_error("Site does not exist");
	}
	if (p == id[p]) { return p; }
	return id[p] = find(id[p]);
}

void WQU::Union(int p, int q) {
	if (p >= numberOfSite || q >= numberOfSite) {
		throw runtime_error("Site does not exist");
	}
	int rp = find(p);
	int rq = find(q);
	if (rp == rq) { return; }
	if (sz[rp] < sz[rq]) {
		id[rp] = rq;
		sz[rq] += sz[rp];
	}
	else {
		id[rq] = rp;
		sz[rp] += sz[rq];
	}
	--count;
}

//測試隨機生成數據最終連在一棵樹上所需的連結條數
int WQU::Count(int n) {
	while (n > numberOfSite) { newSite(); }
	while (get_count() != 1) {
		int p = rand() % n;
		int q = rand() % n;
		cout << p << ' ' << q << endl;
		if (!connected(p, q)) {
			Union(p, q);
		}
	}
	int cnt = 0;
	for (size_t i = 0; i < id.size(); ++i) {
		if (i != id[i]) {
			++cnt;
		}
	}
	return cnt;
}

//創建一個參與連結的新節點，返回它的值
int WQU::newSite() {
	id.push_back(numberOfSite);
	sz.push_back(1);
	++count;
	return numberOfSite++;
}

int main() {
	int n;
	cin >> n;
	WQU temp;
	cout << temp.Count(n);
	return 0;
}

find採用遞歸壓縮路徑。在不改變根節點的情況下，令被查找過的節點指向其根節點，從而降低被查找過的節點的深度，進而降低再次查找時的時間複雜度。