目錄
一、概念
?編輯
二、應(yīng)用場景--“連接”問題（屬于同一Qu
三、實(shí)現(xiàn)思路
?四、如何存儲(chǔ)數(shù)據(jù)
五、定義接口
1.初始化（init）
2.其他
isSame（）
六、抽象類
六、Quick Find【v1 所在集合的所有元素都指向?v2 的根節(jié)點(diǎn)】
1.Union
1.Union圖解
2.注意點(diǎn)：?
3.代碼實(shí)現(xiàn)
2.find?
1.find圖解
2.代碼實(shí)現(xiàn)
3.完整代碼
七、（常用）Quick Union【v1 的根節(jié)點(diǎn)指向?v2 的根節(jié)點(diǎn)】
1.Union
1.注意點(diǎn)
2.Quick Union圖解
3.代碼實(shí)現(xiàn)
2.find
代碼實(shí)現(xiàn)
3.完整代碼
八、Quick Union的優(yōu)化
1.簡介
?2.方案一：基于size的優(yōu)化【元素少的樹 嫁接到 元素多的樹】
?編輯?
3.方案二：基于rank的優(yōu)化【矮的樹 嫁接到 高的樹】
九、路徑壓縮（Path Compression）
1.什么是路徑壓縮？
2.代碼實(shí)現(xiàn)
十、路徑分裂（Path Spliting）
1.概念
?2.代碼實(shí)現(xiàn)
十一、路徑減半（Path Halving）
1.概念
2.代碼實(shí)現(xiàn)
十二、總結(jié)
一、概念
并查集(Disjoint Set)是一種可以動(dòng)態(tài)維護(hù)若干個(gè)不重疊的集合，并支持合并與查詢兩種操作的一種數(shù)據(jù)結(jié)構(gòu)。按照一般的思路，在一些有N個(gè)元素的集合應(yīng)用問題中，我們通常是在開始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中，這樣時(shí)間復(fù)雜度就太高啦。而并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。
并查集支持查找一個(gè)元素所屬的集合以及兩個(gè)元素各自所屬的集合的合并等運(yùn)算,當(dāng)給出兩個(gè)元素的一個(gè)無序?qū)?a,b)時(shí),需要快速“合并” a 和 b 分別所在的集合,這期間需要反復(fù)“查找”某元素所在的集合?！安ⅰ?、“查”和“集” 3 個(gè)字由此而來。在這種數(shù)據(jù)類型中,n個(gè)不同的元素被分為若干組。每組是一個(gè)集合,這種集合叫分離集合,稱之為并查集。
二、應(yīng)用場景--“連接”問題（屬于同一Qu
并查集是一種非常精巧而實(shí)用的數(shù)據(jù)結(jié)構(gòu)，它注意用于處理一些不相交集合的合并溫問題。一些常見的用途有連通子圖，求最小生成樹Kruskal算法和求最近公共祖先（LCA）。
三、實(shí)現(xiàn)思路
?四、如何存儲(chǔ)數(shù)據(jù)
假設(shè)并查集處理的數(shù)據(jù)都是整型，那么可以用整型數(shù)組來存儲(chǔ)數(shù)據(jù)。
- 數(shù)組索引代表元素值
- 索引對(duì)應(yīng)的值代表這個(gè)元素的根節(jié)點(diǎn)
并查集是可以用數(shù)組實(shí)現(xiàn)的樹形結(jié)構(gòu)（二叉堆、優(yōu)先級(jí)隊(duì)列也是可以用數(shù)組實(shí)現(xiàn)的樹形結(jié)構(gòu)）?
五、定義接口
1.初始化（init）
初始化時(shí)，每個(gè)元素各自屬于一個(gè)單元素集合
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;
}
}
2.其他
/**
* 查找v所屬的集合(根結(jié)點(diǎn))
*/
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);
}六、抽象類
這是個(gè)并查集的抽象類，后面的所有并查集都將繼承它。
package union;
/**
* 這是個(gè)并查集的抽象類，后面的所有并查集都將繼承它。
*/
public abstract class UnionFind {
// 初始一維數(shù)組存放父節(jié)點(diǎn)
protected int[] parents;
//初始化
public UnionFind(int capacity){
if (capacity<0){
throw new IllegalArgumentException("capacity must be >=1");
}
// 創(chuàng)建一個(gè)capacity的數(shù)組容量大小存放父節(jié)點(diǎn)
parents=new int[capacity];
//將初始化，自己作為父節(jié)點(diǎn)
for (int i=0;i<parents.length;i++){
parents[i]=i;
}
}
public abstract void union(int v1,int v2);
/**
* 檢查v1，v2是否屬于同一個(gè)集合
* @param v1
* @param v2
* @return
*/
public boolean isSame(int v1,int v2){
return find(v1)==find(v2);
}
/**
* 查找v所屬的集合（根節(jié)點(diǎn)）
* @param v
* @return
*/
public abstract int find(int v);
// 判斷v是否越界
protected void rangeCheck(int v){
if (v<0 || v>=parents.length){
throw new IllegalArgumentException("v is out of bounds");
}
}
}
六、Quick Find【v1 所在集合的所有元素都指向?v2 的根節(jié)點(diǎn)】
1.Union
1.Union圖解
2.注意點(diǎn)：?
1）將v1的根節(jié)點(diǎn)修改成v2的根節(jié)點(diǎn)，同時(shí)要將v1的根節(jié)點(diǎn)的根節(jié)點(diǎn)全部修改為v2的根節(jié)點(diǎn)。
2）union 時(shí)間復(fù)雜度：O(n)
3）樹的高度最高為2
3.代碼實(shí)現(xiàn)
/**
* 將v1所在集合的所有元素都嫁接到v2的父節(jié)點(diǎn)上
* 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){
//如果跟p1是同一個(gè)父節(jié)點(diǎn)，則將其父節(jié)點(diǎn)修改為p2的
parents[i] = p2;
}
}
}2.find?
1.find圖解
2.代碼實(shí)現(xiàn)
/**
* 查找v所屬的集合（根節(jié)點(diǎn)）
* @param v
* @return
*/
public int find(int v){
rangeCheck(v);
return parents[v];
}3.完整代碼
UnionFind_QuickFind?
package union;
/**
* 查找（Find）的時(shí)間復(fù)雜度：O(1)
* 合并（Union）的時(shí)間復(fù)雜度：O(n)
*/
public class UnionFind_QuickFind extends UnionFind{
public UnionFind_QuickFind(int capacity) {
super(capacity);
}
/**
* 查找v所屬的集合（根節(jié)點(diǎn)）
* @param v
* @return
*/
public int find(int v){
rangeCheck(v);
return parents[v];
}
public void union(int v1,int v2){
// p1:表示v1的父節(jié)點(diǎn)
int p1=find(v1);
// p2：表示v2的父節(jié)點(diǎn)
int p2=find(v2);
if (p1==p2) return;
// 到此處則v1和v2不是同一個(gè)父節(jié)點(diǎn)
for (int i=0;i<parents.length;i++){
// 遍歷所有的父節(jié)點(diǎn)，如果該父節(jié)點(diǎn)和v1表示，要將其全部修改為v2的父節(jié)點(diǎn)（p2）
if (parents[i]==p1){
parents[i]=p2;
}
}
}
}
七、（常用）Quick Union【v1 的根節(jié)點(diǎn)指向?v2 的根節(jié)點(diǎn)】
1.Union
1.注意點(diǎn)
1）Quick Find 的?
union(v1, v2)：讓?v1 所在集合的所有元素都指向?v2 的根節(jié)點(diǎn)。2）Quick Union 的?
union(v1, v2)：讓?v1 的根節(jié)點(diǎn)指向?v2 的根節(jié)點(diǎn)?。(與Quick Find進(jìn)行對(duì)比)3）樹的最大高度超過2
2.Quick Union圖解
?
3.代碼實(shí)現(xiàn)
/**
* 將v1的根節(jié)點(diǎn)嫁接到v2的根節(jié)點(diǎn)上
*/
@Override
public void union(int v1, int v2) {
int p1=find(v1);
int p2=find(v2);
if (p1==p2){
return;
}
// 將p1指向p2的父節(jié)點(diǎn)【也就是p1的父節(jié)點(diǎn)為p2的父節(jié)點(diǎn)】
parents[p1]=p2;
}2.find
當(dāng)當(dāng)前節(jié)點(diǎn)值和父節(jié)點(diǎn)的值相等的時(shí)候，說明該節(jié)點(diǎn)是根節(jié)點(diǎn)【v==parents[i]】
代碼實(shí)現(xiàn)
/**
* 通過parents鏈表不斷向上查找，直到根節(jié)點(diǎn)
* @param v
* @return
*/
@Override
public int find(int v) {
rangeCheck(v);
//當(dāng)v不跟父節(jié)點(diǎn)的值相等，則表示還未找到根節(jié)點(diǎn)
while (v!=parents[v]){
v=parents[v];
}
return v;
}3.完整代碼
QuionFind_QuickUnion
package union;
/**
* 查找（Find）的時(shí)間復(fù)雜度：O(logn), 可以優(yōu)化至 O(??(??)), α(??) < 5
* 合并（Union）的時(shí)間復(fù)雜度：O(logn), 可以優(yōu)化至 O(??(??)), α(??) < 5
*/
public class QuionFind_QuickUnion extends UnionFind{
public QuionFind_QuickUnion(int capacity) {
super(capacity);
}
/**
* 將v1所在的根節(jié)點(diǎn) 嫁接到v2的根節(jié)點(diǎn)上
* @param v1
* @param v2
*/
@Override
public void union(int v1, int v2) {
int p1=find(v1);
int p2=find(v2);
if (p1==p2){
return;
}
// 將p1指向p2的父節(jié)點(diǎn)【也就是p1的父節(jié)點(diǎn)為p2的父節(jié)點(diǎn)】
parents[p1]=p2;
}
/**
* 通過parents鏈表不斷向上查找，直到根節(jié)點(diǎn)
* @param v
* @return
*/
@Override
public int find(int v) {
rangeCheck(v);
//當(dāng)v不跟父節(jié)點(diǎn)的值相等，則表示還未找到根節(jié)點(diǎn)
while (v!=parents[v]){
v=parents[v];
}
return v;
}
}
八、Quick Union的優(yōu)化
1.簡介
?2.方案一：基于size的優(yōu)化【元素少的樹 嫁接到 元素多的樹】
不是固定的讓某一棵樹嫁接到另一棵樹，讓元素少的樹 嫁接到 元素多的樹。
package union;
/**
* Quick Union--基于size的優(yōu)化
*/
public class UnionFind_QuickUnion_Size extends UnionFind{
// 該數(shù)組存放以size[i]為根節(jié)點(diǎn)的節(jié)點(diǎn)個(gè)數(shù)
private int[] sizes;
public UnionFind_QuickUnion_Size(int capacity) {
super(capacity);
sizes=new int[capacity];
for (int i=0;i<sizes.length;i++){
// 初始化一個(gè)根節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn)【就是它本身】
sizes[i]=1;
}
}
/**
* 將v1所在的根節(jié)點(diǎn) 嫁接到v2的根節(jié)點(diǎn)上
* @param v1
* @param v2
*/
@Override
public void union(int v1, int v2) {
int p1=find(v1);
int p2=find(v2);
if (p1==p2){
return;
}
//如果v1所在的樹的長度<v2所在的樹的長度，則將v1嫁接到v2上
if (sizes[p1]<sizes[p2]){
parents[p1]=p2;
sizes[p2]+=sizes[p1];
}else { //如果v1所在的樹的長度>v2所在的樹的長度，則將v2嫁接到v1上
parents[p2]=p1;
sizes[p1]+=sizes[p2];
}
}
/**
* 通過parents鏈表不斷向上查找，直到根節(jié)點(diǎn)
* @param v
* @return
*/
@Override
public int find(int v) {
rangeCheck(v);
//當(dāng)v不跟父節(jié)點(diǎn)的值相等，則表示還未找到根節(jié)點(diǎn)
while (v!=parents[v]){
v=parents[v];
}
return v;
}
}
?
3.方案二：基于rank的優(yōu)化【矮的樹 嫁接到 高的樹】
package union;
/**
* Quick Union--基于rank的優(yōu)化
*/
public class UnionFind_QuickUnion_Rank extends UnionFind{
// 該數(shù)組存放以rank[i]為存放高度
private int[] ranks;
public UnionFind_QuickUnion_Rank(int capacity) {
super(capacity);
ranks=new int[capacity];
for (int i=0;i<ranks.length;i++){
// 初始化一個(gè)根節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn)【就是它本身】
ranks[i]=1;
}
}
/**
* 將v1所在的根節(jié)點(diǎn) 嫁接到v2的根節(jié)點(diǎn)上
* @param v1
* @param v2
*/
@Override
public void union(int v1, int v2) {
int p1=find(v1);
int p2=find(v2);
if (p1==p2){
return;
}
if(ranks[p1] < ranks[p2]){ //從矮的到高的樹的總體高度不變
parents[p1] = p2;
}else if(ranks[p1] > ranks[p2]){
parents[p2] = p1;
}else{ // ranks[p1] == ranks[p2]
//誰嫁接誰都可以
parents[p1] = p2;//嫁接到p2
ranks[p2] += 1;
}
}
/**
* 通過parents鏈表不斷向上查找，直到根節(jié)點(diǎn)
* @param v
* @return
*/
@Override
public int find(int v) {
rangeCheck(v);
//當(dāng)v不跟父節(jié)點(diǎn)的值相等，則表示還未找到根節(jié)點(diǎn)
while (v!=parents[v]){
v=parents[v];
}
return v;
}
}
九、路徑壓縮（Path Compression）
雖然有了基于 rank 的優(yōu)化，樹會(huì)相對(duì)平衡一點(diǎn)，但是隨著 union 次數(shù)的增多：樹的高度依然會(huì)越來越高，導(dǎo)致 find 操作變慢，尤其是底層節(jié)點(diǎn) (因?yàn)?find 是不斷向上找到根節(jié)點(diǎn)) 。
1.什么是路徑壓縮？
在 find 時(shí)使路徑上的所有節(jié)點(diǎn)都指向根節(jié)點(diǎn)
?
2.代碼實(shí)現(xiàn)
該類繼承了?UnionFind_QU_R，表明它是在 Quick Union 的 rank 優(yōu)化的基礎(chǔ)上，再優(yōu)化?
package union;
/**
* Quick Union - 基于rank的優(yōu)化 - 路徑壓縮(Path Compression)
*/
public class UnionFind_QuickUnion_rank_PathCompression extends UnionFind_QuickUnion_Rank{
public UnionFind_QuickUnion_rank_PathCompression(int capacity) {
super(capacity);
}
@Override
public int find(int v) { //v==1,parents[v]==2
rangeCheck(v);
if (parents[v]!=v){ //表示還沒有找到根節(jié)點(diǎn)
parents[v]=find(parents[v]);//將根節(jié)點(diǎn)賦值
}
return parents[v];
}
}
十、路徑分裂（Path Spliting）
1.概念
使路徑上的每個(gè)節(jié)點(diǎn)都指向其祖父節(jié)點(diǎn)（parent的parent）
?2.代碼實(shí)現(xiàn)
該類繼承了?UnionFind_QU_R，表明它是在 Quick Union 的 rank 優(yōu)化的基礎(chǔ)上
package union;
/**
* Quick Union - 基于rank的優(yōu)化 - 路徑分裂(Path Spliting)
*/
public class UnionFind_QuickUnion_rank_PathSpliting extends UnionFind_QuickUnion_Rank{
public UnionFind_QuickUnion_rank_PathSpliting(int capacity) {
super(capacity);
}
@Override
public int find(int v){
rangeCheck(v);
while(v != parents[v]){
// 將2保留下來，如果不保留，則2直接消失
int p = parents[v];
// parents[parents[v]]：找到v的祖父節(jié)點(diǎn)
parents[v] = parents[parents[v]];
v = p;
}
return parents[v];
}
}
十一、路徑減半（Path Halving）
1.概念
使路徑上每隔一個(gè)節(jié)點(diǎn)就指向其祖父節(jié)點(diǎn)（parent的parent）
?文章來源地址http://www.zghlxwxcb.cn/news/detail-408138.html
2.代碼實(shí)現(xiàn)
該類繼承了?UnionFind_QU_R，表明它是在 Quick Union 的 rank 優(yōu)化的基礎(chǔ)上，再優(yōu)化
package union;
/**
* Quick Union - 基于rank的優(yōu)化 - 路徑減半(Path Halving)
*/
public class UnionFind_QuickUnion_rank_PathHalving extends UnionFind_QuickUnion_Rank{
public UnionFind_QuickUnion_rank_PathHalving(int capacity) {
super(capacity);
}
@Override
public int find(int v){
rangeCheck(v);
while(v != parents[v]){
parents[v] = parents[parents[v]];
v = parents[v];
}
return v;
}
}
十二、總結(jié)
文章來源：http://www.zghlxwxcb.cn/news/detail-408138.html
?
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】--并查集的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
