find演算法

⑴ 如何檢測社交網路中兩個人是否是朋友關系（union-find演算法）

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

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

好了，言歸正傳。

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

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

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

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

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

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

如果兩個觸點在不同的分量中，union操作會使兩個分量歸並。一開始我們有N個分量（每個觸點表示一個分量），將兩個分量歸並之後數量減一。

抽象實現如下：

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

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

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

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

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

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

union-find演算法只能判斷出給定的兩個整旦敬橋數是否是相連的，無法給出具體達到的路徑；後期我們聊到圖演算法可以給出具體的路徑

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

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

⑵ 使用加權規則和壓縮規則實現UNION和FIND演算法

UNION(1,2);UNION(3,4);UNION(5,6);UNION(7,8);UNION(1,3);UNION(5,7);
FIND(8); 輸出結果慎梁虧是5；
UNION(1,5);
FIND(8); 輸出結果是1.
我所理解的Find（i）演算法是將含有i的parent暫時（在合寬神並的過程中的父母）記住，然後繼續合並一些集合之後在進行查找，就可以在剛渣攔剛所求得的parent的基礎上繼續查找，提高了效率。