您好,登錄后才能下訂單哦!
這篇文章主要介紹“java并查集怎么實(shí)現(xiàn)”,在日常操作中,相信很多人在java并查集怎么實(shí)現(xiàn)問題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”java并查集怎么實(shí)現(xiàn)”的疑惑有所幫助!接下來,請(qǐng)跟著小編一起來學(xué)習(xí)吧!
并查集:一種樹型數(shù)據(jù)結(jié)構(gòu),用于解決一些不相交集合的合并及查詢問題。例如:有n個(gè)村莊,查詢2個(gè)村莊之間是否有連接的路,連接2個(gè)村莊
兩大核心:
查找 (Find) : 查找元素所在的集合
合并 (Union) : 將兩個(gè)元素所在集合合并為一個(gè)集合
并查集有兩種常見的實(shí)現(xiàn)思路
快查(Quick Find)
查找(Find)的時(shí)間復(fù)雜度:O(1)
合并(Union)的時(shí)間復(fù)雜度:O(n)
快并(Quick Union)
查找(Find)的時(shí)間復(fù)雜度:O(logn)可以優(yōu)化至O(a(n))a(n)< 5
合并(Union)的時(shí)間復(fù)雜度:O(logn)可以優(yōu)化至O(a(n))a(n)< 5
使用數(shù)組實(shí)現(xiàn)樹型結(jié)構(gòu),數(shù)組下標(biāo)為元素,數(shù)組存儲(chǔ)的值為父節(jié)點(diǎn)的值
創(chuàng)建抽象類Union Find
public abstract class UnionFind { int[] parents; /** * 初始化并查集 * @param capacity */ public UnionFind(int capacity){ if(capacity < 0) { throw new IllegalArgumentException("capacity must be >=0"); } //初始時(shí)每一個(gè)元素父節(jié)點(diǎn)(根結(jié)點(diǎn))是自己 parents = new int[capacity]; for(int i = 0; i < parents.length;i++) { parents[i] = i; } } /** * 檢查v1 v2 是否屬于同一個(gè)集合 */ public boolean isSame(int v1,int v2) { return find(v1) == find(v2); } /** * 查找v所屬的集合 (根節(jié)點(diǎn)) */ public abstract int find(int v); /** * 合并v1 v2 所屬的集合 */ public abstract void union(int v1, int v2); // 范圍檢查 public void rangeCheck(int v) { if(v<0 || v > parents.length) throw new IllegalArgumentException("v is out of capacity"); } }
以Quick Find實(shí)現(xiàn)的并查集,樹的高度最高為2,每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就是根節(jié)點(diǎn)
public class UnionFind_QF extends UnionFind { public UnionFind_QF(int capacity) { super(capacity); } // 查 @Override public int find(int v) { rangeCheck(v); return parents[v]; } // 并 將v1所在集合并到v2所在集合上 @Override public void union(int v1, int v2) { // 查找v1 v2 的父(根)節(jié)點(diǎn) int p1= find(v1); int p2 = find(v2); if(p1 == p2) return; //將所有以v1的根節(jié)點(diǎn)為根節(jié)點(diǎn)的元素全部并到v2所在集合上 即父節(jié)點(diǎn)改為v2的父節(jié)點(diǎn) for(int i = 0; i< parents.length; i++) { if(parents[i] == p1) { parents[i] = p2; } } } }
public class UnionFind_QU extends UnionFind { public UnionFind_QU(int capacity) { super(capacity); } //查某一個(gè)元素的根節(jié)點(diǎn) @Override public int find(int v) { //檢查下標(biāo)是否越界 rangeCheck(v); // 一直循環(huán)查找節(jié)點(diǎn)的根節(jié)點(diǎn) while (v != parents[v]) { v = parents[v]; } return v; } //V1 并到 v2 中 @Override public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; //將v1 根節(jié)點(diǎn) 的 父節(jié)點(diǎn) 修改為 v2的根結(jié)點(diǎn) 完成合并 parents[p1] = p2; } }
并查集常用快并來實(shí)現(xiàn),但是快并有時(shí)會(huì)出現(xiàn)樹不平衡的情況
有兩種優(yōu)化思路:rank優(yōu)化,size優(yōu)化
核心思想:元素少的樹 嫁接到 元素多的樹
public class UniondFind_QU_S extends UnionFind{ // 創(chuàng)建sizes 數(shù)組記錄 以元素(下標(biāo))為根結(jié)點(diǎn)的元素(節(jié)點(diǎn))個(gè)數(shù) private int[] sizes; public UniondFind_QU_S(int capacity) { super(capacity); sizes = new int[capacity]; //初始都為 1 for(int i = 0;i < sizes.length;i++) { sizes[i] = 1; } } @Override public int find(int v) { rangeCheck(v); while (v != parents[v]) { v = parents[v]; } return v; } @Override public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; //如果以p1為根結(jié)點(diǎn)的元素個(gè)數(shù) 小于 以p2為根結(jié)點(diǎn)的元素個(gè)數(shù) p1并到p2上,并且更新p2為根結(jié)點(diǎn)的元素個(gè)數(shù) if(sizes[p1] < sizes[p2]) { parents[p1] = p2; sizes[p2] += sizes[p1]; // 反之 則p2 并到 p1 上,更新p1為根結(jié)點(diǎn)的元素個(gè)數(shù) }else { parents[p2] = p1; sizes[p1] += sizes[p2]; } } }
基于size優(yōu)化還有可能會(huì)導(dǎo)致樹不平衡
核心思想:矮的樹 嫁接到 高的樹
public class UnionFind_QU_R extends UnionFind_QU { // 創(chuàng)建rank數(shù)組 ranks[i] 代表以i為根節(jié)點(diǎn)的樹的高度 private int[] ranks; public UnionFind_QU_R(int capacity) { super(capacity); ranks = new int[capacity]; for(int i = 0;i < ranks.length;i++) { ranks[i] = 1; } } public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; // p1 并到 p2 上 p2為根 樹的高度不變 if(ranks[p1] < ranks[p2]) { parents[p1] = p2; // p2 并到 p1 上 p1為根 樹的高度不變 } else if(ranks[p1] > ranks[p2]) { parents[p2] = p1; }else { // 高度相同 p1 并到 p2上,p2為根 樹的高度+1 parents[p1] = p2; ranks[p2] += 1; } } }
基于rank優(yōu)化,隨著Union次數(shù)的增多,樹的高度依然會(huì)越來越高 導(dǎo)致find操作變慢
有三種思路可以繼續(xù)優(yōu)化 :路徑壓縮、路徑分裂、路徑減半
在find時(shí)使路徑上的所有節(jié)點(diǎn)都指向根節(jié)點(diǎn),從而降低樹的高度
/** * Quick Union -基于rank的優(yōu)化 -路徑壓縮 * */ public class UnionFind_QU_R_PC extends UnionFind_QU_R { public UnionFind_QU_R_PC(int capacity) { super(capacity); } @Override public int find(int v) { rangeCheck(v); if(parents[v] != v) { //遞歸 使得從當(dāng)前v 到根節(jié)點(diǎn) 之間的 所有節(jié)點(diǎn)的 父節(jié)點(diǎn)都改為根節(jié)點(diǎn) parents[v] = find(parents[v]); } return parents[v]; } }
雖然能降低樹的高度,但是實(shí)現(xiàn)成本稍高
使路徑上的每個(gè)節(jié)點(diǎn)都指向其祖父節(jié)點(diǎn)
/** * Quick Union -基于rank的優(yōu)化 -路徑分裂 * */ public class UnionFind_QU_R_PS extends UnionFind_QU_R { public UnionFind_QU_R_PS(int capacity) { super(capacity); } @Override public int find(int v) { rangeCheck(v); while(v != parents[v]) { int p = parents[v]; parents[v] = parents[parents[v]]; v = p; } return v; } }
使路徑上每隔一個(gè)節(jié)點(diǎn)就指向其祖父節(jié)點(diǎn)
/** * Quick Union -基于rank的優(yōu)化 -路徑減半 * */ public class UnionFind_QU_R_PH extends UnionFind_QU_R { public UnionFind_QU_R_PH(int capacity) { super(capacity); } public int find(int v) { rangeCheck(v); while(v != parents[v]) { parents[v] = parents[parents[v]]; v = parents[v]; } return v; } }
使用Quick Union + 基于rank的優(yōu)化 + 路徑分裂 或 路徑減半
可以保證每個(gè)操作的均攤時(shí)間復(fù)雜度為O(a(n)) , a(n) < 5
到此,關(guān)于“java并查集怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。