您好,登錄后才能下訂單哦!
這篇文章跟大家分析一下“Java數(shù)據(jù)結(jié)構(gòu)中如何進(jìn)行并查集的實(shí)現(xiàn)”。內(nèi)容詳細(xì)易懂,對“Java數(shù)據(jù)結(jié)構(gòu)中如何進(jìn)行并查集的實(shí)現(xiàn)”感興趣的朋友可以跟著小編的思路慢慢深入來閱讀一下,希望閱讀后能夠?qū)Υ蠹矣兴鶐椭?。下面跟著小編一起深入學(xué)習(xí)“Java數(shù)據(jù)結(jié)構(gòu)中如何進(jìn)行并查集的實(shí)現(xiàn)”的知識(shí)吧。
并查集就是將原本不在一個(gè)集合里面的內(nèi)容合并到一個(gè)集合中。
在實(shí)際的場景中用處不多。
除了出現(xiàn)在你需要同時(shí)去幾個(gè)集合里面查詢,避免出現(xiàn)查詢很多次,從而放在一起查詢的情況。
下面簡單實(shí)現(xiàn)一個(gè)例子,我們來舉例說明一下什么是并查集,以及究竟并查集解決了什么問題。
package com.chaojilaji.book.andcheck; public class AndCheckSet { public static Integer getFather(int[] father, int u) { if (father[u] != u) { father[u] = getFather(father, father[u]); } return father[u]; } public static void join(int[] father,int x, int y) { int fx = getFather(father,x); int fy = getFather(father,y); if (fx != fy){ father[fx] = fy; } } public static void main(String[] args) { int n = 10; int[] a = new int[n]; for (int i = 0;i<n;i++){ a[i] = i; // 初始化定義一百個(gè)集合 } for (int i=0;i<n;i++){ System.out.println(i+" "+getFather(a, i)); // 對于每個(gè)集合,父節(jié)點(diǎn)都是自己 } } }
首先,我們定義了兩個(gè)函數(shù),分別為getFather和join,分別表示獲取u所在集合的根以及合并兩個(gè)集合。
先來看看getFather方法
public static Integer getFather(int[] father, int u) { if (father[u] != u) { father[u] = getFather(father, father[u]); } return father[u]; }
是找出值u所在集合的根節(jié)點(diǎn)是多少。一般來說,father[u]如果等于u本身,那么說明u所在節(jié)點(diǎn)就是根節(jié)點(diǎn),而這個(gè)算法是直到相等才退出,也就是說,對于從u到根節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)的father都被直接置為根節(jié)點(diǎn),同時(shí)返回了當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)。
然后來看看join方法
public static void join(int[] father,int x, int y) { int fx = getFather(father,x); int fy = getFather(father,y); if (fx != fy){ father[fx] = fy; } }
分別找出x和y兩個(gè)節(jié)點(diǎn)所在集合的根節(jié)點(diǎn),如果根節(jié)點(diǎn)不一樣,則將其中一個(gè)節(jié)點(diǎn)的father節(jié)點(diǎn)置為另一個(gè)節(jié)點(diǎn)即可,這樣就合并成了一個(gè)集合。
public static void main(String[] args) { int n = 10; int[] a = new int[n]; for (int i = 0;i<n;i++){ a[i] = i; // 初始化定義n個(gè)集合 } for (int i=0;i<n;i++){ System.out.println(i+" "+getFather(a, i)); // 對于每個(gè)集合,父節(jié)點(diǎn)都是自己 } System.out.println("-------------------------"); join(a,0,1); // 合并 0 和 1 for (int i=0;i<n;i++){ System.out.println(i+" "+getFather(a, i)); } // 由于合并了0和1,所以集合變成了9個(gè),節(jié)點(diǎn)0和節(jié)點(diǎn)1的根都是節(jié)點(diǎn)1 System.out.println("-------------------------"); join(a,2,3); // 合并 2 和 3 for (int i=0;i<n;i++){ System.out.println(i+" "+getFather(a, i)); } // 由于合并了2和3,所以集合變成8個(gè),節(jié)點(diǎn)2和節(jié)點(diǎn)3的根都是節(jié)點(diǎn)3 System.out.println("-------------------------"); join(a,1,3); // 合并 1 和 3 for (int i=0;i<n;i++){ System.out.println(i+" "+getFather(a, i)); } // 由于合并了1和3,所以集合變成7個(gè),節(jié)點(diǎn)0,1,2,3的根都是節(jié)點(diǎn)3 }
首先,我們定義了n個(gè)集合,這n個(gè)集合的值是0~n-1,然后此時(shí)他們的父節(jié)點(diǎn)均等于他們本身,所以這就是n個(gè)獨(dú)立的集合,結(jié)果如下
0的父節(jié)點(diǎn)為 0 1的父節(jié)點(diǎn)為 1 2的父節(jié)點(diǎn)為 2 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9
然后調(diào)用 join(a,0,1)合并0集合和1集合,再輸出節(jié)點(diǎn)父集合情況為
0的父節(jié)點(diǎn)為 1 1的父節(jié)點(diǎn)為 1 2的父節(jié)點(diǎn)為 2 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9
可以看見,由于合并了0和1,所以集合變成了9個(gè),節(jié)點(diǎn)0和節(jié)點(diǎn)1的根都是節(jié)點(diǎn)1。
然后調(diào)用 join(a,2,3) 合并2集合和3集合,輸出節(jié)點(diǎn)父集合情況為
0的父節(jié)點(diǎn)為 1 1的父節(jié)點(diǎn)為 1 2的父節(jié)點(diǎn)為 3 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9
可以看見,由于合并了2和3,所以集合變成8個(gè),節(jié)點(diǎn)2和節(jié)點(diǎn)3的根都是節(jié)點(diǎn)3。
最后,我們再調(diào)用join(a,1,3) 合并1集合和3集合,輸出節(jié)點(diǎn)父集合情況為
0的父節(jié)點(diǎn)為 3 1的父節(jié)點(diǎn)為 3 2的父節(jié)點(diǎn)為 3 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9
可以看出來,由于合并了1和3,所以集合變成7個(gè),節(jié)點(diǎn)0,1,2,3的根都是節(jié)點(diǎn)3。
代碼的層面來講,并查集很好實(shí)現(xiàn)。但是我們卻也可以發(fā)現(xiàn),其應(yīng)用場景似乎非常局限。
首先,我們需要定義出一個(gè)father[x] = x的數(shù)組,然后我們再去合并。似乎很難想到應(yīng)用場景。
那么我們可以想象一個(gè)場景,現(xiàn)在有個(gè)網(wǎng)絡(luò)拓?fù)鋱D,里面有n和網(wǎng)絡(luò)設(shè)施設(shè)備,然后又給了你這n個(gè)設(shè)施設(shè)備之間的連接關(guān)系,問你一共有多少個(gè)局部聯(lián)通網(wǎng)。
對于這個(gè)問題,我們就可以首先定義每個(gè)設(shè)備自己跟自己相連,然后每出現(xiàn)一條邊,就對這兩個(gè)設(shè)備采取join操作。最終我們在遍歷完所有的節(jié)點(diǎn),得到多少個(gè)不同的father,即表示有多少個(gè)不同的局部聯(lián)通網(wǎng)。
這樣的問題還可以延伸到我們的人際交友圈,首先每個(gè)人都是單獨(dú)的集合,在不斷認(rèn)識(shí)人的過程中,產(chǎn)生連通性。最終讓你確認(rèn)一共有多少個(gè)不互通的人際圈。
所以你會(huì)發(fā)現(xiàn),這本質(zhì)上就是求圖論中連通塊的個(gè)數(shù)。
Java主要應(yīng)用于:1. web開發(fā);2. Android開發(fā);3. 客戶端開發(fā);4. 網(wǎng)頁開發(fā);5. 企業(yè)級(jí)應(yīng)用開發(fā);6. Java大數(shù)據(jù)開發(fā);7.游戲開發(fā)等。
關(guān)于Java數(shù)據(jù)結(jié)構(gòu)中如何進(jìn)行并查集的實(shí)現(xiàn)就分享到這里啦,希望上述內(nèi)容能夠讓大家有所提升。如果想要學(xué)習(xí)更多知識(shí),請大家多多留意小編的更新。謝謝大家關(guān)注一下億速云網(wǎng)站!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。