Java數(shù)據(jù)機構(gòu)中關(guān)于并查集的詳解
本期文章源碼:GitHub
一文徹底搞懂《并查集》!
概念
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合的合并及查詢問題(即所謂的并、查)。比如說,我們可以用并查集來判斷一個森林中有幾棵樹、某個節(jié)點是否屬于某棵樹等。
具體的用法,我們會以下一篇文章《圖的相關(guān)算法》中,有一個克魯斯卡爾算法,用于生成最小生成樹,會用到并查集。
并查集的主要作用是求連通分支數(shù)(如果一個圖中所有點都存在可達關(guān)系(直接或間接相連),則此圖的連通分支數(shù)為1;如果此圖有兩大子圖各自全部可達,則此圖的連通分支數(shù)為2……)
在現(xiàn)實生活中,也是存在著并查集的一些概念,例如最近《天龍八部》里的人物關(guān)系,可能你并不認識丐幫的一些小人物,但是你一定認識丐幫幫主喬峰。當你看見一個叫花子,你就會想到他的老大就是幫主喬峰,像這樣的場景,就有了一定的歸屬感, 會自動的認為叫花子就是跟丐幫合并在一起的……
說簡單一點,并查集就是將一些數(shù)據(jù)進行分類,這樣數(shù)據(jù)為一組,那些數(shù)據(jù)為另一組。如何判斷其中兩個數(shù)據(jù),在不在一個組?我們就會去找每個組的代表,看這兩個數(shù)據(jù)的代表是不是同一個?如果是,那就是在一個組;如果不是,那就不在一個組。所以并查集的大致框架就是下面這樣:
//并查集大致框架---代碼中的數(shù)據(jù)(Node),可以是其他,比如二叉樹節(jié)點、圖的邊、節(jié)點等等 抽象的數(shù)據(jù) public class UnionSet { private HashMap<Node, Node> fatherMap; //key表示當前這個數(shù)據(jù),value表示這個數(shù)據(jù)的代表(父親)是誰 private HashMap<Node, Integer> sizeMap; //表示當前這個組(集合)的大小 public UnionSet() { //構(gòu)造方法 fatherMap = new HashMap<>(); sizeMap = new HashMap<>(); } public void makeSet(List<Node> list) { //生成初始化狀態(tài)的并查集,剛開始每個數(shù)據(jù)都是獨立的 } public boolean isSameSet(Node node1, Node node2) { //判斷當前這兩個數(shù)據(jù),是不是一個組的? } private Node findFather(Node node) { //查找這個數(shù)據(jù),它那個組的代表(父親)是誰? } public void union(Node node1, Node node2) { //將這兩個數(shù)據(jù),放到一個組 } }
上面就是大致的框架,就是幾個方法:初始化并查集、判斷是不是一個組、查找代表、合并到一個組
。四個方法,就是并查集。簡不簡單?
并查集在判斷兩個數(shù)據(jù),是否在一個組時,時間復(fù)雜度能做到O(1),所以這種數(shù)據(jù)結(jié)構(gòu)還是非常有用的。
實現(xiàn)
初始化并查集
我們首先從第一個方法:初始化并查集開始。
傳入進去的參數(shù)不一定是List,也可以是Collection等等,表示一組數(shù)據(jù)即可! 首先我們的成員變量只有兩個,分別是存儲節(jié)點的代表 和 當前這個組的大小。初始化時,我們分別認為 每個節(jié)點是自己一個人一組的,也就是說,自己一個組,代表就是自己本身;大小的話,就是自己本身咯,也就是1。
//初始化并查集 public void makeSet(List<Node> list) { if (list == null) { return; } fatherMap.clear(); sizeMap.clear(); //先將表清空 //遍歷list,把每一個節(jié)點,都放入哈希表中 for (Node node : list) { fatherMap.put(node, node); //第一個參數(shù)是節(jié)點本身,第二個參數(shù)就是這個組的代表 sizeMap.put(node, 1); //第一個參數(shù)是這個組的代表,第二個參數(shù)是大小 } }
判斷是不是同一個組
isSameSet
比較簡單,就是判斷兩個數(shù)據(jù)所在的組的代表,是不是用一個數(shù)據(jù)即可!如果代表是同一個人,那就是在一個組,反之就不是!
//判斷是不是同一個組 public boolean isSameSet(Node node1, Node node2) { if (node1 == null || node2 == null) { return false; } return findFather(node1) == findFather(node2); //查找各自的代表節(jié)點,看是不是同一個。 }
查找當前節(jié)點的代表節(jié)點
findFather
,我自己覺得算是并查集的核心,也這是這個方法,是并查集的查找的時間復(fù)雜度能在O(1)的主要因素。
思路就跟二叉樹向上查找根結(jié)點的思路一樣,也就是說,在fatherMap中一直查找,直到一個節(jié)點的代表節(jié)點(父節(jié)點)是它自己本身時,此時就查找完了;然后最關(guān)鍵的一步,就是路徑壓縮,在我們向上查找的過程中,我們需要記錄沿途的所有節(jié)點,在查找結(jié)束后,我們將沿途的這些節(jié)點,在fatherMap中的進行修改,直接將這些節(jié)點的代表節(jié)點,寫成這個組的代表節(jié)點,可能聽糊涂了,看下圖:
這樣的設(shè)計,就能使查找的時間復(fù)雜度控制在O(1)。
//查找代表節(jié)點,并做路徑壓縮 private Node findFather(Node node) { if (node == null) { return null; } //查找代表節(jié)點 Stack<Node> path = new Stack<>(); //存儲沿途的節(jié)點 while (node != fatherMap.get(node)) { //代表節(jié)點不是自己本身,就繼續(xù)查找 path.push(node); node = fatherMap.get(node); } //路徑壓縮 while (!path.isEmpty()) { Node tmp = path.pop(); fatherMap.put(tmp, node); //此時的node,就是這個組的代表節(jié)點 } return node; }
合并操作
終于來到了最后的操作:合并。合并也比較簡單,記住一個要點:小組掛在大組的下面。也就是說,這一個節(jié)點所在的組要小一點,我們直接將他“掛”在另一個組的下面。說簡單一點:這一個組的代表節(jié)點的vaule域,直接指向另一個組的代表節(jié)點。
//合并操作 public void union(Node node1, Node node2) { if (node1 == null || node2 == null) { return; } int node1Size = sizeMap.get(node1); int node2Size = sizeMap.get(node2); //分別得到兩個節(jié)點所在組的大小 Node node1Father = fatherMap.get(node1); Node node2Father = fatherMap.get(node2); //分別拿到兩個節(jié)點的代表節(jié)點 if (node1Father != node2Father) { //兩個節(jié)點,不在同一個組,就合并 if (node1Size < node2Size) { //node1 掛在 node2 fatherMap.put(node1Father, node2Father); sizeMap.put(node2Father, node1Size + node2Size); //新的組,大小是原來兩個組的和 sizeMap.remove(node1Father); //小組的數(shù)據(jù),就不需要了,刪除 } else { //node2 掛在 node1 //跟上面操作類似 fatherMap.put(node2Father, node1Father); sizeMap.put(node1Father, node1Size + node2Size); sizeMap.remove(node1Father); } } }
上面就是并查集的所有操作了,是不是很簡單呢?
好啦,本期更新到此就結(jié)束啦,同學(xué)們,下期見?。?!
到此這篇關(guān)于Java數(shù)據(jù)機構(gòu)中關(guān)于并查集的詳解的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)機構(gòu) 并查集內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Mybatis-plus自動填充不生效或自動填充數(shù)據(jù)為null原因及解決方案
本文主要介紹了Mybatis-plus自動填充不生效或自動填充數(shù)據(jù)為null原因及解決方案,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05java數(shù)據(jù)結(jié)構(gòu)算法稀疏數(shù)組示例詳解
這篇文章主要為大家介紹了java數(shù)據(jù)結(jié)構(gòu)算法稀疏數(shù)組示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-06-06Spring的編程式事務(wù)TransactionTemplate的用法詳解
TransactionTemplate提供了一種在代碼中進行編程式事務(wù)管理的方式,使開發(fā)人員能夠在方法級別定義事務(wù)的開始和結(jié)束點,本文介紹了Spring框架中TransactionTemplate的用法,感興趣的朋友跟隨小編一起看看吧2023-07-07Java接口返回省市區(qū)樹形結(jié)構(gòu)的實現(xiàn)
本文主要介紹了Java接口返回省市區(qū)樹形結(jié)構(gòu)的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01Java日期時間及日期相互轉(zhuǎn)換實現(xiàn)代碼
這篇文章主要介紹了Java日期時間及日期相互轉(zhuǎn)換實現(xiàn)代碼,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-12-12Java的super關(guān)鍵字與instanceof運算符使用方法
這篇文章主要介紹了Java的super關(guān)鍵字與instanceof運算符使用方法,是Java入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09