您好,登錄后才能下訂單哦!
這篇文章主要介紹Java實現(xiàn)快速并查集的方法,文中介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們一定要看完!
在一些應用的問題中,需將n個不同的元素劃分成一組不相交的集合。開始時,每個元素自成一格單元素集合,然后按一定順序?qū)儆谕唤M的元素的集合合并。其間要反復用到查詢某個元素屬于哪個集合的運算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集。
1. 并查集的概述
并查集的數(shù)學模型是一組不相交的動態(tài)集合的集合S={A,B,C,...},它支持以下的運算:
(1)union(A,B):將集合A和B合并,其結(jié)果取名為A或B;
(2)find(x):找出包含元素x的集合,并返回該集合的名字。
在并查集中需要兩個類型的參數(shù):集合名字的類型和元素的類型。在許多情況下,可以用整數(shù)作為集合的名字。如果集合中共有n個元素,可以用范圍【1:n】以內(nèi)的整數(shù)表示元素。實現(xiàn)并查集的一個簡單方法是使用數(shù)組表示元素及其所屬子集的關系。其中,用數(shù)組下標表示元素,用數(shù)組單元記錄該元素所屬的子集名字。如果元素類型不是整型,則可以先構(gòu)造一個映射,將每個元素映射成一個整數(shù)。這種映射可以用散列表或其他方式實現(xiàn)。
2. 并查集的實現(xiàn)
采用數(shù)結(jié)構(gòu)實現(xiàn)并查集的基本思想是,每個集合用一棵樹表示。樹的結(jié)點用于存儲集合中的元素名。每個樹結(jié)點還存放一個指向其父結(jié)點的指針。數(shù)根結(jié)點處的元素代表該數(shù)所表示的集合。利用映射可以找到集合中所對應的數(shù)結(jié)點。
父親數(shù)組是實現(xiàn)上述數(shù)結(jié)構(gòu)的有效方法。
Java實現(xiàn)代碼:
public class UnionFind { Node[] node; //父親數(shù)組 //并查集中的結(jié)點 private static class Node{ int parent; boolean root; private Node(){ parent = 1; root = true; } } //將每個元素初始化為一顆單結(jié)點樹 public UnionFind(int n){ node = new Node[n + 1]; for(int e= 0; e <= n; e++){ node[e] = new Node(); } } }
find運算就是從元素e相應的結(jié)點走到樹根處,找出所在集合的名字。
public int find(int e){ while(!node[e].root){ e = node[e].parent; } return e; }
union運算,合并兩個集合,只要將表示其中一個集合的樹的數(shù)根改為表示另一個集合的樹的數(shù)根的兒子結(jié)點。
public void union(int a, int b){ node[a].parent += node[b].parent; node[b].root = false; node[b].parent = a; }
3. 快速并查集的實現(xiàn)
容易看出,在最壞情況下,合并可能使n個結(jié)點的樹退化成一條鏈,導致對所有元素各執(zhí)行一次find將耗時O(n^2)??勺龀鲆韵赂倪M來加速find運算。
1.)小樹合并到大樹
在union操作中,將表示小樹的數(shù)根改為表示大樹的數(shù)根的兒子結(jié)點。于是并查集中每個結(jié)點至多被移動O(logn)次,從而每個結(jié)點到數(shù)根的距離不會超過O(logn)。所有,每次find運算只需O(logn)時間。
/* * 合并兩個集合(加速) * 將表示小樹的數(shù)根改為表示大樹的數(shù)根的兒子結(jié)點 */ public void union(int a, int b){ if(node[a].parent < node[b].parent){ node[b].parent += node[a].parent; node[a].root = false; node[a].parent = a; }else{ node[a].parent += node[b].parent; node[b].root = false; node[b].parent = a; } }
2.)路徑壓縮技術
在執(zhí)行find時,實際上找到了從一個結(jié)點到數(shù)根的一條路徑。路徑壓縮就是把這條路上所有的結(jié)點都提升1層,以加快找到根結(jié)點的時間。
/* * find運算(加速) * 從元素e相應的結(jié)點走到樹根處,找出所在集合的名字 */ public int find(int e){ int current = e, p ,gp; /*排除當前結(jié)點或其父結(jié)點為根的情況后,加速find*/ if(node[current].root){ return current; } p = node[current].parent; if(node[current].root){ return p; } gp = node[current].parent; while(true){ node[current].parent = gp; if(node[gp].root){ return gp; } current = p; p = gp; gp = node[p].parent; } }
以上是Java實現(xiàn)快速并查集的方法的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關知識,歡迎關注億速云行業(yè)資訊頻道!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。