并查集
借鑒百度百科的解釋，并查集就是在一些有N個元素的集合問題中，開始的時候讓每個元素成為自己的集合，然后按照一定的順序將屬于同一組的元素所在的集合進行合并（合并的是集合），在合并的期間需要方法查找元素所在的集合，并查集的原理比較簡單，解決的問題的特點是看似并不復雜，但資料量極大，例如：圖的連通子圖問題，一個圖里面有幾個連通子圖，判斷這幅圖是否連通等，若用正常的資料結構來描述，往往時空復雜度會過高，并查集是一種樹形資料結構，用于處理一些不相交集合的合并和查詢問題，并查集的原理就是朋友的朋友就是我的朋友，
基本
正如名字表達的那樣，并查集需要合并和查詢集合，所以并查集一般需要一個陣列和兩個函式：int[] parent, int find(int element)和void unionElements(int firstOne, int secondOne)，
parent陣列用來記錄每個元素的前導點，也就是確定該元素所在的集合id；find函式用來查找某元素所在的集合id；unionElements用來合并不同的集合，其基本程序如下圖所示，
實作代碼：
public class UnionFind1 {
private int[] id; //存盤元素的root
private int size; //并查集大小
//構建新的并查集
public UnionFind1(int size) {
this.size = size;
id = new int[size];
for (int i=0; i<size; i++)
id[i] = i; //每個元素都指向自己
}
//查看元素所屬的集合
public int find(int element) {
return id[element];
}
//判斷是否屬于同一集合
public boolean isConnected(int firElement, int secElement) {
return find(firElement) == find(secElement);
}
//合并兩個集合
public void unionElements(int firElement, int secElement) {
int firUnion = find(firElement);
int secUnion = find(secElement);
if(firUnion != secUnion) {
//合并效率低下，合并一次是O(n)的復雜度
for(int i=0; i<this.size; i++) {
if(id[i] == firUnion) {
id[i] = secUnion;
}
}
}
}
//列印元素
private void printSet() {
for (int id : this.id)
System.out.print(id + " ");
System.out.println();
}
//入口
public static void main(String[] args) {
int n = 10;
UnionFind1 union = new UnionFind1(n);
System.out.println("初始化: ");
union.printSet();
System.out.println("連接5 6");
union.unionElements(5, 6);
System.out.println("連接1 2 ");
union.unionElements(1, 2);
System.out.println("連接2 3");
union.unionElements(2, 3);
System.out.println("連接1 4");
union.unionElements(1, 4);
System.out.println("連接1 5");
union.unionElements(1, 5);
System.out.println("最終結果: ");
union.printSet();
System.out.println("1 6 是否連接: " + union.isConnected(1, 6));
System.out.println("1 8 是否連接: " + union.isConnected(1, 8));
System.out.println("1 4 是否連接: " + union.isConnected(1, 4));
}
}
Output:
初始化:
0 1 2 3 4 5 6 7 8 9
連接5 6
連接1 2
連接2 3
連接1 4
連接1 5
最終結果:
0 6 6 6 6 6 6 7 8 9
1 6 是否連接: true
1 8 是否連接: false
1 4 是否連接: true
優化1
上述的并查集合并時候的復雜度是O(n)的，現在對其改進，在合并的時候，當前集合的爸爸去當別人的兒子，當前集合其他元素的爸爸(前導點)不變，這樣的話，需要改變查找的方式，因為對某個集合來說，最終的爸爸只有一個，例如對于下面這個陣列集合：
元素：0 1 2 3
爸爸：1 2 3 3
查找元素0和1的"爸爸"，應該是3而不是1和2，所以find的尋找方式應該改變，應該找到最終的爸爸（元素和爸爸是同一個的點），這種方式合并的復雜度下降了，但是find的復雜度增加了，
實作代碼：
public class UnionFind2 {
private int[] id;
private int size;
public UnionFind2(int size) {
this.size = size;
id = new int[size];
for (int i=0; i<size; i++)
id[i] = i;
}
//找到最終的root
public int find(int element) {
while(element != id[element])
element = id[element];
return element;
}
public boolean isConnected(int firElement, int secElement)
{ return find(firElement) == find(secElement); }
public void unionElements(int firElement, int secElement) {
int firUion = find(firElement);
int secUion = find(secElement);
if (firUion == secUion)
return;
id[firUion] = secUion;
}
private void printSet() {
for (int id : this.id)
System.out.print(id + " ");
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind2 union = new UnionFind2(n);
System.out.println("初始化: ");
union.printSet();
System.out.println("連接5 6");
union.unionElements(5, 6);
System.out.println("連接1 2 ");
union.unionElements(1, 2);
System.out.println("連接2 3");
union.unionElements(2, 3);
System.out.println("連接1 4");
union.unionElements(1, 4);
System.out.println("連接1 5");
union.unionElements(1, 5);
System.out.println("最終結果: ");
union.printSet();
System.out.println("1 6 是否連接: " + union.isConnected(1, 6));
System.out.println("1 8 是否連接: " + union.isConnected(1, 8));
System.out.println("1 4 是否連接: " + union.isConnected(1, 4));
}
}
Output:
初始化:
0 1 2 3 4 5 6 7 8 9
連接5 6
連接1 2
連接2 3
連接1 4
連接1 5
最終結果:
0 2 3 4 6 6 6 7 8 9
1 6 是否連接: true
1 8 是否連接: false
1 4 是否連接: true
優化2
優化1的修改方案，是犧牲查詢函式的復雜度來換取合并函式復雜度的下降，并且還有引入一個新的問題，就是合并后的陣列很可能會達到線性鏈表的狀態，例如：
元素：0 1 2 3 4 5 6 7 8 9
爸爸：1 2 3 4 5 6 7 8 9 9
這樣畫出來的連通子圖是一條鏈表來的，這種原因是合并方式不合理造成的，所以第二種優化的方式可從合并方式下手，引入一個權重來衡量到底誰應該當爸爸，有兩種權重可供選擇，一種是重量，一種是高度，
重量（數目）：就是集合爸爸底下有多少數目的子孫；高度（代，箭頭數）：就是集合爸爸底下有多少代子孫，
基于重量，誰重誰當爸爸，
實作代碼：
public class UnionFind3 {
private int[] id;
private int[] weight;
private int size;
public UnionFind3(int size) {
this.size = size;
this.id = new int[size];
this.weight = new int[size];
for (int i=0; i<size; i++) {
this.id[i] = i;
this.weight[i] = 1; //初始化為1個元素
}
}
public int find(int element) {
while(element != id[element]){
element = id[element];
}
return element;
}
public boolean isConnected(int firElement, int secElement) {
return find(firElement) == find(secElement);
}
public void unionElements(int firElement, int secElement) {
int firUion = find(firElement);
int secUion = find(secElement);
if(firUion == secUion)
return;
//減少find的查找時間，誰重誰是爸爸
if(weight[firUion] > weight[secUion]) {
id[secUion] = firUion;
weight[firUion] += weight[secUion];
}
else {
id[firUion] = secUion;
weight[secUion] += weight[firUion];
}
}
private void printSet() {
for (int id : this.id)
System.out.print(id + " ");
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind3 union = new UnionFind3(n);
System.out.println("初始化: ");
union.printSet();
System.out.println("連接5 6");
union.unionElements(5, 6);
System.out.println("連接1 2 ");
union.unionElements(1, 2);
System.out.println("連接2 3");
union.unionElements(2, 3);
System.out.println("連接1 4");
union.unionElements(1, 4);
System.out.println("連接1 5");
union.unionElements(1, 5);
System.out.println("最終結果: ");
union.printSet();
System.out.println("1 6 是否連接: " + union.isConnected(1, 6));
System.out.println("1 8 是否連接: " + union.isConnected(1, 8));
System.out.println("1 4 是否連接: " + union.isConnected(1, 4));
}
}
Output:
初始化:
0 1 2 3 4 5 6 7 8 9
連接5 6
連接1 2
連接2 3
連接1 4
連接1 5
最終結果:
0 2 2 2 2 6 2 7 8 9
1 6 是否連接: true
1 8 是否連接: false
1 4 是否連接: true
基于高度，誰子孫代數多誰當爸爸，
實作代碼：
public class UnionFind4 {
private int[] id;
private int[] height;
private int size;
public UnionFind4(int size) {
this.size = size;
this.id = new int[size];
this.height = new int[size];
for (int i=0; i<size; i++) {
id[i] = i;
height[i] = 1;
}
}
public int find(int element) {
while(element != id[element])
element = id[element];
return element;
}
public boolean isConnected(int fir, int sec) {
return find(fir) == find(sec);
}
public void unionElements(int fir, int sec) {
int firUion = find(fir);
int secUion = find(sec);
if(firUion == secUion)
return;
//使用高度決定誰被誰插入，減少find的時間
if(height[firUion] > height[secUion])
id[secUion] = firUion;
else if(height[firUion] < height[secUion])
id[firUion] = secUion;
else {
id[firUion] = secUion;
height[secUion]++;
}
}
private void printSet() {
for (int id : this.id)
System.out.print(id + " ");
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind4 union = new UnionFind4(n);
System.out.println("初始化: ");
union.printSet();
System.out.println("連接5 6");
union.unionElements(5, 6);
System.out.println("連接1 2 ");
union.unionElements(1, 2);
System.out.println("連接2 3");
union.unionElements(2, 3);
System.out.println("連接1 4");
union.unionElements(1, 4);
System.out.println("連接1 5");
union.unionElements(1, 5);
System.out.println("最終結果: ");
union.printSet();
System.out.println("1 6 是否連接: " + union.isConnected(1, 6));
System.out.println("1 8 是否連接: " + union.isConnected(1, 8));
System.out.println("1 4 是否連接: " + union.isConnected(1, 4));
}
}
Output:
初始化:
0 1 2 3 4 5 6 7 8 9
連接5 6
連接1 2
連接2 3
連接1 4
連接1 5
最終結果:
0 2 6 2 2 6 6 7 8 9
1 6 是否連接: true
1 8 是否連接: false
1 4 是否連接: true
優化3
不管是基于重量還是高度，并查集還是有可能會出現深的節點，這時候可以進行干預，進行路徑壓縮，具體的方法就是在每一步的查詢操作進行壓縮，讓當前元素的"爸爸"升級成"爺爺"，這種路徑壓縮只能在基于重量的并查集實作，因為在壓縮的時候，當前集合的重量是不會變的，但是高度很有可能改變，
實作代碼：
public class UnionFind5 {
private int[] id;
private int[] weight;
private int size;
public UnionFind5(int size) {
this.size = size;
this.id = new int[size];
this.weight = new int[size];
for (int i=0; i<size; i++) {
id[i] = i;
weight[i] = 1;
}
}
//路徑壓縮，指向自己爸爸的爸爸，進一步壓縮
public int find(int element) {
while(element != id[element]) {
id[element] = id[id[element]];
element = id[element];
}
return element;
}
public boolean isConnected(int fir, int sec) {
return find(fir) == find(sec);
}
public void unionElements(int fir, int sec) {
int firUion = find(fir);
int secUion = find(sec);
if (firUion == secUion)
return;
if (weight[firUion] > weight[secUion]) {
id[secUion] = firUion;
weight[firUion] += weight[secUion];
}
else {
id[firUion] = secUion;
weight[secUion] += weight[firUion];
}
}
private void printSet() {
for (int id : this.id)
System.out.print(id + " ");
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind5 union = new UnionFind5(n);
System.out.println("初始化: ");
union.printSet();
System.out.println("連接5 6");
union.unionElements(5, 6);
System.out.println("連接1 2 ");
union.unionElements(1, 2);
System.out.println("連接2 3");
union.unionElements(2, 3);
System.out.println("連接1 4");
union.unionElements(1, 4);
System.out.println("連接1 5");
union.unionElements(1, 5);
System.out.println("最終結果: ");
union.printSet();
System.out.println("1 6 是否連接: " + union.isConnected(1, 6));
System.out.println("1 8 是否連接: " + union.isConnected(1, 8));
System.out.println("1 4 是否連接: " + union.isConnected(1, 4));
}
}
Output:
初始化:
0 1 2 3 4 5 6 7 8 9
連接5 6
連接1 2
連接2 3
連接1 4
連接1 5
最終結果:
0 2 2 2 2 6 2 7 8 9
1 6 是否連接: true
1 8 是否連接: false
1 4 是否連接: true
這篇博客主要是方便自己日后復習和查看使用，主要參考了下面這篇博客：
https://www.cnblogs.com/noKing/p/8018609.html
下面還有一篇關于并查集的概念解釋得不錯的概念分享給大家：
https://www.cnblogs.com/-new/p/6662301.html
謝謝大家，這是本人的第一篇技術博客，歡迎大家批評指正，轉載注明出處就行，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228733.html
標籤：其他