一族展、奇怪的樹結(jié)構(gòu)
由子節(jié)點指向父節(jié)點,連接問題 Connectivity Problem
網(wǎng)絡(luò)中節(jié)點間的連接狀態(tài)
- 網(wǎng)絡(luò)是個抽象的概念：例如用戶之間形成之間的網(wǎng)絡(luò)
- 數(shù)學(xué)中集合類的實現(xiàn)
連接問題和路徑問題相比悬垃，連接問題比路徑問題要回答的問題少？
元素個數(shù)是固定的占卧，沒有添加和刪除操作遗菠，只針對已存在的進(jìn)行分析
并查集實現(xiàn)的接口
UF
public interface UF {
int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}
二联喘、Quick Find查找很快(第一版)
描述：略，請直接觀察代碼
查找的復(fù)雜度為O(1)
// 我們的第一版Union-Find
public class UnionFind1 implements UF{
private int[] id;
public UnionFind1(int size) {
id = new int[size];
for (int i = 0; i < size; i++) {
id[i] = i;
}
}
@Override
public int getSize() {
return id.length;
}
// 查找元素P所對應(yīng)的集合編號
private int find(int p) {
if(p < 0 || p >= id.length)
throw new IllegalArgumentException("error");
return id[p];
}
// 查看元素p和元素q是否屬于一個集合
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// 合并元素p和元素q所屬的集合
@Override
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if(pID == qID)
return;
for (int i = 0; i < id.length; i++) {
if(id[i] == pID)
id[i] = qID;
}
}
}
Quick Union連接很快(第二版)
描述：將所有元素抽象為一個靜態(tài)數(shù)組辙纬，數(shù)組的索引對應(yīng)為自己的id豁遭，初始化所有id的值都是保存的自己的索引，可以理解為初始化時所有的元素都指向的為自己贺拣，當(dāng)將兩個id進(jìn)行 連接操作(unionElements) 的時候,分別查詢自己保存的id,然后再查詢以此id為索引保存的值是否等于查詢的索引蓖谢，如果不相等則繼續(xù)找，直到查詢到索引與保存的索引相等譬涡；分別找到索引后 【這里有優(yōu)化空間,詳見第三版】 隨機(jī)將一個索引的值保存為另一個索引闪幽。對應(yīng)的 查詢操作(isConnected) 就變得十分簡單了，找到指向的根節(jié)點(對應(yīng)索引的位置保存的為當(dāng)前索引)涡匀，并判斷是否相等盯腌。
儲存方式還是數(shù)組，但是邏輯層面是森林(很多樹),子節(jié)點指向父節(jié)點渊跋，一層一層腊嗡，直到一個節(jié)點指向自己
public class UnionFind2 implements UF{
private int[] parent;
public UnionFind2(int size) {
this.parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
@Override
public int getSize() {
return parent.length;
}
/**查找過程中着倾，查找圓度p所對應(yīng)的集合編號
* O(h) 復(fù)雜度拾酝，h為數(shù)的高度*/
private int find(int p) {
if(p < 0 && p >= parent.length)
throw new IllegalArgumentException("error");
while (p != parent[p])
p = parent[p];
return p;
}
/**查看元素p和p是否所屬一個集合
* O(h) 復(fù)雜度，h為數(shù)的高度*/
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
/** 合并元素p和元素q所屬的集合
* O(h)復(fù)雜度卡者，h為數(shù)的高度*/
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot != qRoot)
parent[pRoot] = qRoot;
}
}
- 第一版與第二版性能的比較蒿囤！(并查集的長度一定)
- 當(dāng)操作并查集的次數(shù)很少的時候，第一版的isConnected的復(fù)雜度為O(1),unionElements的復(fù)雜度為O(n),主要的性能消耗在了unionElements崇决，耗時長材诽；第二版的兩個操作的復(fù)雜度都是O(h) ,h為該相關(guān)樹的高度，樹的深度很淺恒傻，總體性能優(yōu)于第一版
- 當(dāng)操作并查集的次數(shù)很多的時候脸侥，優(yōu)于JVM對于數(shù)組遍歷操作有很好的優(yōu)化，性能不會差好多盈厘，但是對于第二版睁枕，此時的數(shù)的深度可能很深了，而且每次根據(jù)索引尋找具體地址進(jìn)行取值會比第一版的遍歷操作要差一些沸手，當(dāng)操作量大了之后就充分體現(xiàn)了外遇，此時第一版的性能總體優(yōu)于第二版
基于size的優(yōu)化 (第三版)
為每個索引保存一個記錄當(dāng)前節(jié)點下對應(yīng)的所有子節(jié)點數(shù)，在unionElements時契吉，將子節(jié)點少的根節(jié)點指向子節(jié)點多的節(jié)點跳仿。從而減少樹的深度，但是捐晶，子節(jié)點少就不一定代表次數(shù)最深深度比子節(jié)點多的最深深度要淺菲语，【更進(jìn)一步優(yōu)化妄辩，請看下面的rank優(yōu)化】
public class UnionFind3 implements UF {
private int[] parent;
private int[] count; // 儲存parent每個節(jié)點下的所有子節(jié)點個數(shù)
public UnionFind3(int size) {
this.parent = new int[size];
this.count = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
count[i] = 1;
}
}
@Override
public int getSize() { return this.parent.length; }
private int find(int p) {
while (p != parent[p])
p = parent[p];
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
if(count[p] < count[q]) {
parent[p] = q;
count[q] += count[p];
} else {
parent[q] = p;
count[p] += count[q];
}
}
}
基于rank的優(yōu)化(終極版a0.5)
基于rank的優(yōu)化，rank[i]表示根節(jié)點為i的數(shù)的高度谨究。
在unionElements時恩袱，將最深度小的數(shù)根節(jié)點指向最深度比較大的根節(jié)點，僅當(dāng)兩顆數(shù)最深度相等時胶哲，隨機(jī)將一棵樹指向另一棵樹畔塔，并且維護(hù)一下這顆數(shù)的最深度(深度自增1，只有此步驟需要維護(hù)樹的最大深度)
public class UnionFind4 implements UF {
private int[] parent;
private int[] rank; // 儲存parent每個節(jié)點下的所有子節(jié)點個數(shù)
public UnionFind4(int size) {
this.parent = new int[size];
this.rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
@Override
public int getSize() { return this.parent.length; }
private int find(int p) {
while (p != parent[p])
p = parent[p];
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
if(rank[p] < rank[q])
parent[p] = q;
else if (rank[q] < rank[p])
parent[q] = p;
else {
parent[p] = q;
rank[q] += 1;
}
}
}
簡單的路徑壓縮Path Compression(終極版a--終極奧義版)
思路：在終極版a0.5上進(jìn)行優(yōu)化鸯屿，在find操作的時候進(jìn)行路徑壓縮,減少深度parent\[p\] = parent\[parent\[p\]\]
如下圖:
路徑壓縮版實在終極版0.5的基礎(chǔ)上的find方法上進(jìn)行了優(yōu)化澈吨，同時，這也導(dǎo)致rank記錄的與樹的最深深度不統(tǒng)一寄摆，但是絲毫不影響基于rank的比較谅辣！這就是為什么叫做rank而不叫depth或者h(yuǎn)eight的原因
public class UnionFind5 implements UF {
private int[] parent;
private int[] rank; // 儲存parent每個節(jié)點下的所有子節(jié)點個數(shù)
public UnionFind5(int size) {
this.parent = new int[size];
this.rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
@Override
public int getSize() { return this.parent.length; }
private int find(int p) {
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("Index is out of bounds!");
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
if(rank[p] < rank[q])
parent[p] = q;
else if (rank[q] < rank[p])
parent[q] = p;
else {
parent[p] = q;
rank[q] += 1;
}
}
}
徹底的路徑壓縮(終極版b，性能略低于終極奧義版)
徹底的路徑壓縮：遞歸實現(xiàn)(只有遞歸到最深處婶恼，才能再一步一步重新定向),還是在find中進(jìn)行操作桑阶，雖然保證了樹的深度永遠(yuǎn)為1，但是勾邦，遞歸的開銷是很大的蚣录，性能上不一定比終極版a要好，這就驗證了有的必有失眷篇！(終極版a雖然不能一次性將深度變?yōu)?,但是在諸多的find操作下萎河，已經(jīng)非常非常靠近1了)
public class UnionFind6 implements UF {
private int[] parent;
private int[] rank; // 儲存parent每個節(jié)點下的所有子節(jié)點個數(shù)
public UnionFind6(int size) {
this.parent = new int[size];
this.rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
@Override
public int getSize() { return this.parent.length; }
private int find(int p) {
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("Index out of bounds.");
// 如果寫成了parent[p] = find(p) 則會形成死循環(huán)
while (p != parent[p]) {
parent[p] = find(parent[p]);
}
return parent[p];
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
if(rank[p] < rank[q])
parent[p] = q;
else if (rank[q] < rank[p])
parent[q] = p;
else {
parent[p] = q;
rank[q] += 1;
}
}
}
更多喝并查集相關(guān)的話題
查詢和連接操作的時間復(fù)雜度都是O(h)蕉饼，但是h與n的關(guān)系是非常非常
復(fù)雜的數(shù)學(xué)關(guān)系虐杯，不需要去深究(我不搞數(shù)學(xué))。
嚴(yán)格意義上昧港，加入路徑壓縮的并查集的
時間復(fù)雜度為O(log*n)----> iterated logarithm
上圖的*是一種遞歸表示擎椰，就和計算機(jī)遞歸過程是一樣的
O(log*n)是一種比O(log*n)更牛逼的，近乎等于O(1)級別
