Java數據結構中如何進行并查集的實現

這篇文章跟大家分析一下“Java數據結構中如何進行并查集的實現”。內容詳細易懂，對“Java數據結構中如何進行并查集的實現”感興趣的朋友可以跟著小編的思路慢慢深入來閱讀一下，希望閱讀后能夠對大家有所幫助。下面跟著小編一起深入學習“Java數據結構中如何進行并查集的實現”的知識吧。

并查集就是將原本不在一個集合里面的內容合并到一個集合中。

在實際的場景中用處不多。

除了出現在你需要同時去幾個集合里面查詢，避免出現查詢很多次，從而放在一起查詢的情況。

下面簡單實現一個例子，我們來舉例說明一下什么是并查集，以及究竟并查集解決了什么問題。

代碼解析

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; // 初始化定義一百個集合
        }
        for (int i=0;i<n;i++){
            System.out.println(i+" "+getFather(a, i)); // 對于每個集合，父節點都是自己
        }
    }
}

首先，我們定義了兩個函數，分別為getFather和join，分別表示獲取u所在集合的根以及合并兩個集合。

先來看看getFather方法

public static Integer getFather(int[] father, int u) {
    if (father[u] != u) {
        father[u] = getFather(father, father[u]);
    }
    return father[u];
}

是找出值u所在集合的根節點是多少。一般來說，father[u]如果等于u本身，那么說明u所在節點就是根節點，而這個算法是直到相等才退出，也就是說，對于從u到根節點的每個節點的father都被直接置為根節點，同時返回了當前節點的根節點。

然后來看看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兩個節點所在集合的根節點，如果根節點不一樣，則將其中一個節點的father節點置為另一個節點即可，這樣就合并成了一個集合。

代碼應用

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個集合
    }
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i)); // 對于每個集合，父節點都是自己
    }
    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個，節點0和節點1的根都是節點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個，節點2和節點3的根都是節點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個，節點0,1,2,3的根都是節點3
}

首先，我們定義了n個集合，這n個集合的值是0~n-1，然后此時他們的父節點均等于他們本身，所以這就是n個獨立的集合，結果如下

0的父節點為 0 1的父節點為 1 2的父節點為 2 3的父節點為 3 4的父節點為 4 5的父節點為 5 6的父節點為 6 7的父節點為 7 8的父節點為 8 9的父節點為 9

然后調用 join(a,0,1)合并0集合和1集合，再輸出節點父集合情況為

0的父節點為 1 1的父節點為 1 2的父節點為 2 3的父節點為 3 4的父節點為 4 5的父節點為 5 6的父節點為 6 7的父節點為 7 8的父節點為 8 9的父節點為 9

可以看見，由于合并了0和1，所以集合變成了9個，節點0和節點1的根都是節點1。
然后調用 join(a,2,3) 合并2集合和3集合，輸出節點父集合情況為

0的父節點為 1 1的父節點為 1 2的父節點為 3 3的父節點為 3 4的父節點為 4 5的父節點為 5 6的父節點為 6 7的父節點為 7 8的父節點為 8 9的父節點為 9

可以看見，由于合并了2和3，所以集合變成8個，節點2和節點3的根都是節點3。
最后，我們再調用join(a,1,3) 合并1集合和3集合，輸出節點父集合情況為

0的父節點為 3 1的父節點為 3 2的父節點為 3 3的父節點為 3 4的父節點為 4 5的父節點為 5 6的父節點為 6 7的父節點為 7 8的父節點為 8 9的父節點為 9

可以看出來，由于合并了1和3，所以集合變成7個，節點0,1,2,3的根都是節點3。

實際應用

代碼的層面來講，并查集很好實現。但是我們卻也可以發現，其應用場景似乎非常局限。
首先，我們需要定義出一個father[x] = x的數組，然后我們再去合并。似乎很難想到應用場景。

那么我們可以想象一個場景，現在有個網絡拓撲圖，里面有n和網絡設施設備，然后又給了你這n個設施設備之間的連接關系，問你一共有多少個局部聯通網。
對于這個問題，我們就可以首先定義每個設備自己跟自己相連，然后每出現一條邊，就對這兩個設備采取join操作。最終我們在遍歷完所有的節點，得到多少個不同的father，即表示有多少個不同的局部聯通網。

這樣的問題還可以延伸到我們的人際交友圈，首先每個人都是單獨的集合，在不斷認識人的過程中，產生連通性。最終讓你確認一共有多少個不互通的人際圈。

所以你會發現，這本質上就是求圖論中連通塊的個數。

Java可以用來干什么

Java主要應用于：1. web開發；2. Android開發；3. 客戶端開發；4. 網頁開發；5. 企業級應用開發；6. Java大數據開發；7.游戲開發等。

關于Java數據結構中如何進行并查集的實現就分享到這里啦，希望上述內容能夠讓大家有所提升。如果想要學習更多知識，請大家多多留意小編的更新。謝謝大家關注一下億速云網站！