Java數據機構中關於並查集的詳解
本期文章源碼:GitHub
一文徹底搞懂《並查集》!
概念
並查集是一種樹型的數據結構,用於處理一些不相交集合的合並及查詢問題(即所謂的並、查)。比如說,我們可以用並查集來判斷一個森林中有幾棵樹、某個節點是否屬於某棵樹等。
具體的用法,我們會以下一篇文章《圖的相關算法》中,有一個克魯斯卡爾算法,用於生成最小生成樹,會用到並查集。
並查集的主要作用是求連通分支數(如果一個圖中所有點都存在可達關系(直接或間接相連),則此圖的連通分支數為1;如果此圖有兩大子圖各自全部可達,則此圖的連通分支數為2……)
在現實生活中,也是存在著並查集的一些概念,例如最近《天龍八部》裡的人物關系,可能你並不認識丐幫的一些小人物,但是你一定認識丐幫幫主喬峰。當你看見一個叫花子,你就會想到他的老大就是幫主喬峰,像這樣的場景,就有瞭一定的歸屬感, 會自動的認為叫花子就是跟丐幫合並在一起的……
說簡單一點,並查集就是將一些數據進行分類,這樣數據為一組,那些數據為另一組。如何判斷其中兩個數據,在不在一個組?我們就會去找每個組的代表,看這兩個數據的代表是不是同一個?如果是,那就是在一個組;如果不是,那就不在一個組。所以並查集的大致框架就是下面這樣:
//並查集大致框架---代碼中的數據(Node),可以是其他,比如二叉樹節點、圖的邊、節點等等 抽象的數據 public class UnionSet { private HashMap<Node, Node> fatherMap; //key表示當前這個數據,value表示這個數據的代表(父親)是誰 private HashMap<Node, Integer> sizeMap; //表示當前這個組(集合)的大小 public UnionSet() { //構造方法 fatherMap = new HashMap<>(); sizeMap = new HashMap<>(); } public void makeSet(List<Node> list) { //生成初始化狀態的並查集,剛開始每個數據都是獨立的 } public boolean isSameSet(Node node1, Node node2) { //判斷當前這兩個數據,是不是一個組的? } private Node findFather(Node node) { //查找這個數據,它那個組的代表(父親)是誰? } public void union(Node node1, Node node2) { //將這兩個數據,放到一個組 } }
上面就是大致的框架,就是幾個方法:初始化並查集、判斷是不是一個組、查找代表、合並到一個組
。四個方法,就是並查集。簡不簡單?
並查集在判斷兩個數據,是否在一個組時,時間復雜度能做到O(1),所以這種數據結構還是非常有用的。
實現
初始化並查集
我們首先從第一個方法:初始化並查集開始。
傳入進去的參數不一定是List,也可以是Collection等等,表示一組數據即可! 首先我們的成員變量隻有兩個,分別是存儲節點的代表 和 當前這個組的大小。初始化時,我們分別認為 每個節點是自己一個人一組的,也就是說,自己一個組,代表就是自己本身;大小的話,就是自己本身咯,也就是1。
//初始化並查集 public void makeSet(List<Node> list) { if (list == null) { return; } fatherMap.clear(); sizeMap.clear(); //先將表清空 //遍歷list,把每一個節點,都放入哈希表中 for (Node node : list) { fatherMap.put(node, node); //第一個參數是節點本身,第二個參數就是這個組的代表 sizeMap.put(node, 1); //第一個參數是這個組的代表,第二個參數是大小 } }
判斷是不是同一個組
isSameSet
比較簡單,就是判斷兩個數據所在的組的代表,是不是用一個數據即可!如果代表是同一個人,那就是在一個組,反之就不是!
//判斷是不是同一個組 public boolean isSameSet(Node node1, Node node2) { if (node1 == null || node2 == null) { return false; } return findFather(node1) == findFather(node2); //查找各自的代表節點,看是不是同一個。 }
查找當前節點的代表節點
findFather
,我自己覺得算是並查集的核心,也這是這個方法,是並查集的查找的時間復雜度能在O(1)的主要因素。
思路就跟二叉樹向上查找根結點的思路一樣,也就是說,在fatherMap中一直查找,直到一個節點的代表節點(父節點)是它自己本身時,此時就查找完瞭;然後最關鍵的一步,就是路徑壓縮,在我們向上查找的過程中,我們需要記錄沿途的所有節點,在查找結束後,我們將沿途的這些節點,在fatherMap中的進行修改,直接將這些節點的代表節點,寫成這個組的代表節點,可能聽糊塗瞭,看下圖:
這樣的設計,就能使查找的時間復雜度控制在O(1)。
//查找代表節點,並做路徑壓縮 private Node findFather(Node node) { if (node == null) { return null; } //查找代表節點 Stack<Node> path = new Stack<>(); //存儲沿途的節點 while (node != fatherMap.get(node)) { //代表節點不是自己本身,就繼續查找 path.push(node); node = fatherMap.get(node); } //路徑壓縮 while (!path.isEmpty()) { Node tmp = path.pop(); fatherMap.put(tmp, node); //此時的node,就是這個組的代表節點 } return node; }
合並操作
終於來到瞭最後的操作:合並。合並也比較簡單,記住一個要點:小組掛在大組的下面。也就是說,這一個節點所在的組要小一點,我們直接將他“掛”在另一個組的下面。說簡單一點:這一個組的代表節點的vaule域,直接指向另一個組的代表節點。
//合並操作 public void union(Node node1, Node node2) { if (node1 == null || node2 == null) { return; } int node1Size = sizeMap.get(node1); int node2Size = sizeMap.get(node2); //分別得到兩個節點所在組的大小 Node node1Father = fatherMap.get(node1); Node node2Father = fatherMap.get(node2); //分別拿到兩個節點的代表節點 if (node1Father != node2Father) { //兩個節點,不在同一個組,就合並 if (node1Size < node2Size) { //node1 掛在 node2 fatherMap.put(node1Father, node2Father); sizeMap.put(node2Father, node1Size + node2Size); //新的組,大小是原來兩個組的和 sizeMap.remove(node1Father); //小組的數據,就不需要瞭,刪除 } else { //node2 掛在 node1 //跟上面操作類似 fatherMap.put(node2Father, node1Father); sizeMap.put(node1Father, node1Size + node2Size); sizeMap.remove(node1Father); } } }
上面就是並查集的所有操作瞭,是不是很簡單呢?
好啦,本期更新到此就結束啦,同學們,下期見!!!
到此這篇關於Java數據機構中關於並查集的詳解的文章就介紹到這瞭,更多相關Java 數據機構 並查集內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++並查集算法簡單詳解
- Java 手寫LRU緩存淘汰算法
- 如何利用Java遞歸解決“九連環”公式
- Java數據結構之鏈表相關知識總結
- Java實現單鏈表SingleLinkedList增刪改查及反轉 逆序等