頭圖

如何檢測社交網絡中兩個人是否是朋友關系(union-find算法)

Silently9527

前言

春節放假會了老家,停更了很多天,這是年后連夜肝出來的第一篇文章,先來聊聊春節放假期間發生的事,這次回家遇到了我學生時代的女神,當年她在我心目中那是

"出淤泥而不染、濯清漣而不妖"

沒想到這次回家遇到了她,身體發福了,心目中女神的形象瞬間碎了,就好像達芬奇再次遇到了蒙娜麗莎

"菡萏香銷翠葉殘"

好了,言歸正傳。

有時候我們可以需要判斷在大型網絡中兩臺計算機是否相連,是否需要建立一條新的連接才能通信;或者是在社交網絡中判斷兩個人是否是朋友關系(相連表示是朋友關系)。在這種應用中,通常我們可能需要處理數百萬的對象和數億的連接,如何能夠快速的判斷出是否相連呢?這就需要使用到union-find算法

概念

相連

假如輸入一對整數,其中每個數字表示的是某種對象(人、地址或者計算機等等),整數對p,q理解為“p與q相連”,相連具有以下特性:

  • 自反性:p與p是相連的
  • 對稱性:如果p與q相連,那么q與p相連
  • 傳遞性:如果p與q相連,q與r相連,那么p與r也相連
對象如何與數字關聯起來,后面我們聊到一種算法符號表

等價類

假設相連是一個種等價關系,那么等價關系能夠將對象劃分為多個等價類,在該算法中,當且僅當兩個對象相連時他們才屬于同一個等價類

觸點

整個網絡中的某種對象稱為觸點

連通分量

將整數對稱為連接,將等價類稱作連通分量或者簡稱分量

動態連通性

union-find算法的目標是當程序從輸入中讀取了整數對p q時,如果已知的所有整數對都不能說明p q是相連的,那么將這一對整數輸出,否則忽略掉這對整數;我們需要設計數據結構來保存已知的所有整數對的信息,判斷出輸入的整數對是否是相連的,這種問題叫做動態連通性問題。

union-find算法API定義

public interface UF {
    void union(int p, int q); //在p與q之間添加一條連接

    int find(int p); //返回p所在分量的標識符

    boolean connected(int p, int q); //判斷出p與q是否存在于同一個分量中

    int count(); //統計出連通分量的數量
}

如果兩個觸點在不同的分量中,union操作會使兩個分量歸并。一開始我們有N個分量(每個觸點表示一個分量),將兩個分量歸并之后數量減一。

抽象實現如下:

public abstract class AbstractUF implements UF {
    protected int[] id;
    protected int count;

    public AbstractUF(int N) {
        count = N;

        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public int count() {
        return count;
    }
}

接下來我們就主要來討論如何實現union方法和find方法

quick-find算法

這種算法的實現思路是在同一個連通分量中所有觸點在id[]中的值都是相同的,判斷是否連通的connected的方法就是判斷id[p]是否等于id[q]。

public class QuickFindImpl extends AbstractUF {
    public QuickFindImpl(int N) {
        super(N);
    }

    @Override
    public int find(int p) {
        return id[p];
    }

    @Override
    public void union(int p, int q) {
        int pId = find(p);
        int qId = find(q);

        if (pId == qId) { //如果相等表示p與q已經屬于同一分量中
            return;
        }

        for (int i = 0; i < id.length; i++) {
            if (id[i] == pId) {
                id[i] = qId; //把分量中所有的值都統一成qId
            }
        }
        count--; //連通分量數減一
    }

}
  • 算法分析:

find()操作顯然是很快的,時間復雜度O(1), 但是union的算法是無法處理大型數據的,因為每次都需要變量整個數組,那么union方法的時間復雜度是O(n)

quick-union算法

為了提高union方法的速度,我們需要考慮另外一種算法;使用同樣的數據結構,只是重新定義id[]表示的意義,每個觸點所對應的id[]值都是在同一分量中的另一個觸點的名稱

在數組初始化之后,每個節點的鏈接都指向自己;id[]數組用父鏈接的形式表示了森林,每一次union操作都會找出每個分量的根節點進行歸并。

public class QuickUnionImpl extends AbstractUF {
    public QuickUnionImpl(int N) {
        super(N);
    }

    @Override
    public int find(int p) {
        //找出p所在分量的根觸點
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p); //找出q p的根觸點
        int qRoot = find(q);
        if (pRoot == qRoot) { //處于同一分量不做處理
            return;
        }
        id[pRoot] = qRoot; //根節點
        count--;
    }

}
  • 算法分析:

看起來quick-union算法比quick-find算法更快,因為union不需要為每對輸入遍歷整個數組,
考慮最佳情況下,find方法只需要訪問一次數組就可以得到根觸點,那么union方法的時間復雜度O(n);
考慮到最糟糕的輸入情況,如下圖:

find方法需要訪問數組n-1次,那么union方法的時間復雜度是O(n2)

加權quick-union算法

為了保證quick-union算法最糟糕的情況不在出現,我需要記錄每一個樹的大小,在進行分量歸并操作時總是把小的樹連接到大的樹上,這種算法構造出來樹的高度會遠遠小于未加權版本所構造的樹高度。

public class WeightedQuickUnionImpl extends AbstractUF {
    private int[] sz;

    public WeightedQuickUnionImpl(int N) {
        super(N);
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            sz[i] = 1;
        }
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p); //找出q p的根觸點
        int qRoot = find(q);
        if (pRoot == qRoot) { //處于同一分量不做處理
            return;
        }
        //小樹合并到大樹
        if (sz[pRoot] < sz[qRoot]) {
            sz[qRoot] += sz[pRoot]; 
            id[pRoot] = qRoot;
        } else {
            sz[pRoot] += sz[qRoot];
            id[qRoot] = pRoot;
        }
        count--;
    }

    @Override
    public int find(int p) {
        //找出p所在分量的根觸點
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }
}
  • 算法分析:

最壞的情況下,每次union歸并的樹都是大小相等的,他們都包含了2的n次方個節點,高度都是n,合并之后的高度變成了n+1,由此可以得出union方法的時間復雜度是O(lgN)

總結

union-find算法只能判斷出給定的兩個整數是否是相連的,無法給出具體達到的路徑;后期我們聊到圖算法可以給出具體的路徑

算法union()find()
quick-find算法N1
quick-union算法樹的高度樹的高度
加權quick-union算法lgNlgN

最后(點關注,不迷路)

文中或許會存在或多或少的不足、錯誤之處,有建議或者意見也非常歡迎大家在評論交流。

最后,寫作不易,請不要白嫖我喲,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore

參考書籍:算法第四版

程序員常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin

完全開源的淘客項目:https://github.com/silently9527/mall-coupons-server

微信公眾號:貝塔學Java

閱讀 3k

貝塔學JAVA
公眾號:貝塔學JAVA Java程序員所需要掌握的核心知識: 集合框架、JVM機制、多線程與并發框架、網絡協議...

公眾號:貝塔學JAVA

317 聲望
64 粉絲
0 條評論

公眾號:貝塔學JAVA

317 聲望
64 粉絲
宣傳欄
一本到在线是免费观看_亚洲2020天天堂在线观看_国产欧美亚洲精品第一页_最好看的2018中文字幕 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>