1.六度分隔理論

?

世界上任何兩個互不相識的人，最多只需要通過6個中間人，就可以建立聯(lián)系。

哈佛大學的社會心理學家米爾格蘭姆于1967設計了一個連鎖信件實驗。他將一套連鎖信件隨機發(fā)送給居住在內(nèi)布拉斯加州奧馬哈的160個人，信中放了一個波士頓股票經(jīng)紀人的名字，并要求每名收信人把這封信寄給自己認為是比較接近這名股票經(jīng)紀人的朋友。這位朋友收到信后，再把信寄給他認為更接近這名股票經(jīng)紀人的朋友。最終，大部分信件都寄到了這名股票經(jīng)紀人手中，每封信平均經(jīng)手6次到達。

例如你認識老王，老王認識李大爺，李大爺又認識某人，如此關(guān)聯(lián)，你和奧巴馬之間，最多只差6個人介紹就可以加微信好友啦。

2.引發(fā)思考

如果我現(xiàn)在知道了所有人的通訊錄好友，我想知道我到底能不能認識老奧，怎么驗證呢？
全球有77億人口，每個人的好友圈也有幾百上千，這樣的數(shù)據(jù)量是很大的，簡單的一個一個的查找是行不通的。

那么問題來了，人口普查哪家強，四川成都找老王。。。
所有的信息數(shù)據(jù)如下表：

轉(zhuǎn)換成圖的形式會比較直觀。如果把2個互相認識的人用線連接起來，問題就轉(zhuǎn)化成：你和老奧之間能否找到一條通路（暫不考慮最短是不是不超過6個人）。

3.問題建模

假設朋友的朋友都是朋友，朋友的敵人也是朋友(或者敵人的朋友還是朋友，whatever...)。

我們把所有直接認識的，或者能間接認識的都放到一個大集合中，建立一個大朋友圈。
問題就變成：老奧在不在我們的大朋友圈里？

如果你的大朋友圈里面有人認識川普，那就要把川普的朋友圈里面的所有人都加進來，形成一個新的朋友圈。

相信敏銳的你已經(jīng)發(fā)現(xiàn)問題的本質(zhì)，這里面只有2個重要的操作，來跟我一起大聲朗讀，并...查...。這就需要一種能高效處理集合的合并與查找的算法，并查集就是專門為這種場景量身定制。

4.算法理論

并查集本質(zhì)是一個森林，里面有很多樹。

每個樹有一個根，以不同的根代表不同的集合。如下,root1,root2代表兩個集合。

如初始時，每個元素都屬于一個獨立的集合，該元素作為根。每個根指向一個虛擬根-n，代表權(quán)重(表示該集合有n個元素)。

更新合并
將權(quán)重小的集合的根指向權(quán)重大的集合的根(此操作是為盡量降低樹的深度)。

查找

判斷2個元素是否屬同一集合，只需向上查找根，再判斷是否相同。
過程中做路徑壓縮，加快下一次查找速度。

5.代碼實現(xiàn)

5.1 查找

int?findFather(int?s)?{int?root?=?s,?temp;//?查找s的最頂層根while?(father[root]?>=?0)?{root?=?father[root];}//?路徑壓縮，提高后續(xù)查找效率while?(s?!=?root)?{temp?=?father[s];father[s]?=?root;s?=?temp;}return?root; }

5.2 合并

void?unionSet(int?s,?int?e)?{int?rootS?=?findFather(s);int?rootE?=?findFather(e);int?weight?=?father[rootS]?+?father[rootE];//?將結(jié)點數(shù)少的集合作為結(jié)點數(shù)多的集合的兒子節(jié)點if?(father[rootS]?>?father[rootE])?{father[rootS]?=?rootE;father[rootE]?=?weight;}?else?{father[rootE]?=?rootS;father[rootS]?=?weight;} }

例題

poj1182，poj1308，poj1456，poj1611

關(guān)注我，漲知識，公眾號：幾何思維

總結(jié)

以上是生活随笔為你收集整理的基于并查集的六度分隔理论的验证与实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。