第java數(shù)據(jù)結(jié)構(gòu)并查集詳解if(v0||vparents.length)

thrownewIllegalArgumentException("visoutofcapacity");

}

2.1QuickFind實(shí)現(xiàn)

以QuickFind實(shí)現(xiàn)的并查集，樹的高度最高為2，每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就是根節(jié)點(diǎn)

publicclassUnionFind_QFextendsUnionFind{

publicUnionFind_QF(intcapacity){

super(capacity);

//查

@Override

publicintfind(intv){

rangeCheck(v);

returnparents[v];

//并將v1所在集合并到v2所在集合上

@Override

publicvoidunion(intv1,intv2){

//查找v1v2的父（根）節(jié)點(diǎn)

intp1=find(v1);

intp2=find(v2);

if(p1==p2)return;

//將所有以v1的根節(jié)點(diǎn)為根節(jié)點(diǎn)的元素全部并到v2所在集合上即父節(jié)點(diǎn)改為v2的父節(jié)點(diǎn)

for(inti=0;iparents.length;i++){

if(parents[i]==p1){

parents[i]=p2;

}

2.2QuickUnion實(shí)現(xiàn)

publicclassUnionFind_QUextendsUnionFind{

publicUnionFind_QU(intcapacity){

super(capacity);

//查某一個(gè)元素的根節(jié)點(diǎn)

@Override

publicintfind(intv){

//檢查下標(biāo)是否越界

rangeCheck(v);

//一直循環(huán)查找節(jié)點(diǎn)的根節(jié)點(diǎn)

while(v!=parents[v]){

v=parents[v];

returnv;

//V1并到v2中

@Override

publicvoidunion(intv1,intv2){

intp1=find(v1);

intp2=find(v2);

if(p1==p2)return;

//將v1根節(jié)點(diǎn)的父節(jié)點(diǎn)修改為v2的根結(jié)點(diǎn)完成合并

parents[p1]=p2;

}

三、優(yōu)化

并查集常用快并來實(shí)現(xiàn)，但是快并有時(shí)會(huì)出現(xiàn)樹不平衡的情況

有兩種優(yōu)化思路：rank優(yōu)化，size優(yōu)化

3.1基于size的優(yōu)化

核心思想：元素少的樹嫁接到元素多的樹

publicclassUniondFind_QU_SextendsUnionFind{

//創(chuàng)建sizes數(shù)組記錄以元素（下標(biāo)）為根結(jié)點(diǎn)的元素（節(jié)點(diǎn)）個(gè)數(shù)

privateint[]sizes;

publicUniondFind_QU_S(intcapacity){

super(capacity);

sizes=newint[capacity];

//初始都為1

for(inti=0;isizes.length;i++){

sizes[i]=1;

@Override

publicintfind(intv){

rangeCheck(v);

while(v!=parents[v]){

v=parents[v];

returnv;

@Override

publicvoidunion(intv1,intv2){

intp1=find(v1);

intp2=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)致樹不平衡

3.2基于rank優(yōu)化

核心思想：矮的樹嫁接到高的樹

publicclassUnionFind_QU_RextendsUnionFind_QU{

//創(chuàng)建rank數(shù)組ranks[i]代表以i為根節(jié)點(diǎn)的樹的高度

privateint[]ranks;

publicUnionFind_QU_R(intcapacity){

super(capacity);

ranks=newint[capacity];

for(inti=0;iranks.length;i++){

ranks[i]=1;

publicvoidunion(intv1,intv2){

intp1=find(v1);

intp2=find(v2);

if(p1==p2)return;

//p1并到p2上p2為根樹的高度不變

if(ranks[p1]ranks[p2]){

parents[p1]=p2;

//p2并到p1上p1為根樹的高度不變

}elseif(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)化：路徑壓縮、路徑分裂、路徑減半

3.2.1路徑壓縮（PathCompression）

在find時(shí)使路徑上的所有節(jié)點(diǎn)都指向根節(jié)點(diǎn)，從而降低樹的高度

*QuickUnion-基于rank的優(yōu)化-路徑壓縮

publicclassUnionFind_QU_R_PCextendsUnionFind_QU_R{

publicUnionFind_QU_R_PC(intcapacity){

super(capacity);

@Override

publicintfind(intv){

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]);

returnparents[v];

}

雖然能降低樹的高度，但是實(shí)現(xiàn)成本稍高

3.2.2路徑分裂（PathSpliting）

使路徑上的每個(gè)節(jié)點(diǎn)都指向其祖父節(jié)點(diǎn)

*QuickUnion-基于rank的優(yōu)化-路徑分裂

publicclassUnionFind_QU_R_PSextendsUnionFind_QU_R{

publicUnionFind_QU_R_PS(intcapacity){

super(capacity);

@Override

publicintfind(intv){

rangeCheck(v);

while(v!=parents[v]){

intp=parents[v];

parents[v]=parents[parents[v]];

v=p;

returnv;

}

3.2.3路徑減半（Path