從并查集Union Find算法談算法解決實(shí)際問(wèn)題的過(guò)程

從并查集Union Find算法談算法解決實(shí)際問(wèn)題的過(guò)程
算法
并查集
算法
尋找路徑

從并查集Union Find算法談算法解決實(shí)際問(wèn)題的過(guò)程算法解決實(shí)際問(wèn)題的一般步驟
 并查集算法概述
 實(shí)際問(wèn)題引出
 問(wèn)題建模
 算法版本一 QuickFind 一货岭、使用數(shù)組的值表示連接關(guān)系
 二扣汪、算法的具體實(shí)現(xiàn)
三砾医、算法分析

算法版本二 QuickUnion 一校镐、在樹(shù)組內(nèi)創(chuàng)建樹(shù)表示連接關(guān)系
 二续语、算法的具體實(shí)現(xiàn)
算法分析

改進(jìn)版本二垂直化到扁平化第一步：帶權(quán)合并
 實(shí)現(xiàn)
再進(jìn)一步：壓縮路徑
 四種算法時(shí)間復(fù)雜度對(duì)比

解決實(shí)際問(wèn)題：鄉(xiāng)村公路暢通工程問(wèn)題描述
 問(wèn)題解決
 代碼說(shuō)明

算法解決實(shí)際問(wèn)題的一般步驟
Steps to developing a usable algorithm.
問(wèn)題建模（Model the problem.）
尋找算法解決問(wèn)題（Find an algorithm to solve it.）
算法的復(fù)雜度評(píng)判（Fast enough? Fits in memory?）
尋找影響時(shí)間或控件復(fù)雜的的原因（If not, figure out why.）
尋找問(wèn)題源頭（Find a way to address the problem.）
迭代上述過(guò)程，直到算法達(dá)標(biāo)（Iterate until satisfied.）

并查集算法概述
給定一個(gè)包含N個(gè)對(duì)象的集合，集合中對(duì)象可以相互連接，實(shí)現(xiàn)如下命令： Union
Union command: 連接兩個(gè)對(duì)象。 Find | Connect
Query: 檢查兩個(gè)對(duì)象是否被連接蓬抄。

[圖片上傳中阅爽。。。（1）] 上圖經(jīng)歷過(guò)的操作如下： union(0,1)
union(1,2)
union(3,4)
union(3,8)
union(4,9)
union(0,5)
union(5,6)
union(1,6)
union(2,7)
此時(shí)根據(jù)此圖：檢查結(jié)果如下： True: connected(0,6)
True: connected(0,5)
False: connected(2,3)
False: connected(6,9)

實(shí)際問(wèn)題引出
如下圖，P和Q兩個(gè)點(diǎn)之間是否存在一條路徑（P，Q是否連通）？

[圖片上傳中。。。（2）]在具體一點(diǎn)，現(xiàn)在要解決的實(shí)際問(wèn)題有如下幾個(gè)：
一張圖片中像素點(diǎn)的連接檢查。
大型網(wǎng)絡(luò)中設(shè)備之間的連接檢查。查找
社交網(wǎng)絡(luò)中的好友關(guān)系。
游戲場(chǎng)景中的路徑檢查。

問(wèn)題建模
復(fù)雜問(wèn)題簡(jiǎn)單化 使用整型數(shù)組來(lái)抽象實(shí)際問(wèn)題库倘。舍棄一些細(xì)節(jié)饱亿，僅僅描述其連接關(guān)系幅恋。 具體的實(shí)現(xiàn) 使用數(shù)組的下標(biāo)了表示問(wèn)題中的某一個(gè)對(duì)象腐巢，使用對(duì)應(yīng)的值存儲(chǔ)連接參數(shù)品追。 進(jìn)一步抽象 A: 連接關(guān)系 如果對(duì)象A和對(duì)象B連接银还，那么Connected(A,B)
返回True
如果對(duì)象A和對(duì)象B連接列吼，B又和C連接，那么Connected(A,C)
, 返回True
B:連接組件 如果集合{p, q, r, t}
中, p,q,r
連接理郑，t
和其他三個(gè)不連接柒爵，則有兩個(gè)連接組件： {p, q, r}
和 {t}

[圖片上傳中。赚爵。棉胀。（3）]
問(wèn)題解決：創(chuàng)建數(shù)組，使用union
方法創(chuàng)建連接組件囱晴，使用find/connected
方法檢查對(duì)象是否在同一個(gè)連接組件中膏蚓。

算法版本一 QuickFind
通過(guò)問(wèn)題建模，確定了數(shù)據(jù)結(jié)構(gòu)和基本方法畸写。解決步驟如下：

一驮瞧、使用數(shù)組的值表示連接關(guān)系
數(shù)據(jù)結(jié)構(gòu) 創(chuàng)建Int數(shù)組 id[N], 在這個(gè)包含N個(gè)元素的數(shù)組id中，如果id[p] 和 id[q]的值相同枯芬，那么p论笔，q是連通的。 查找方法 檢查兩個(gè)對(duì)象對(duì)應(yīng)的編號(hào)下的值是否一樣千所。 連接方法 合并p到q狂魔，修改所有值為id[p]的元素的值為id[q]

[圖片上傳中。淫痰。最楷。（4）]
union(6,1)

[圖片上傳中。待错。籽孙。（5）]

二、算法的具體實(shí)現(xiàn)

/* Quick Find 數(shù)據(jù)結(jié)構(gòu)：* 優(yōu)點(diǎn)：查找操作比較快,只需要執(zhí)行一次* 缺點(diǎn)：合并操作效率慢火俄，可能需要nn次數(shù)組讀取 */public class QuickFindUF{private int[] id;public QuickFindUF(int N){id = new int[N];for (int i = 0; i < N; i++ )id[i] = i;}//查找：檢查是否連通就是比較兩個(gè)點(diǎn)對(duì)應(yīng)的值public boolean connected(int p, int q){ return id[p] == id[q]; }//合并：合并的本質(zhì)就是設(shè)置相同的值public void union(int p, int q){int pid = id[p];int qid = id[q];for (int i = 0; i > id.length; i++)if (id[i] == pid) id[i] = qid;}}

三犯建、算法分析
初始化 初始化的時(shí)候，算法需要遍歷整個(gè)數(shù)組瓜客，時(shí)間負(fù)載度為

查找在查找操作中适瓦，僅僅需要訪問(wèn)數(shù)組的兩個(gè)元素即可,程序執(zhí)行效率的時(shí)間復(fù)雜度為常數(shù)

竿开。合并合并操作在這一版本的算法中，需要遍歷整個(gè)數(shù)組,時(shí)間復(fù)雜度為

最壞的情況 當(dāng)需要連接

個(gè)點(diǎn)的時(shí)候玻熙，算法需要遍歷數(shù)組

次否彩。當(dāng)前CPU每秒可以執(zhí)行

條指令;內(nèi)存內(nèi)可以存儲(chǔ)

個(gè)字節(jié)的內(nèi)容;讀取內(nèi)存內(nèi)所有內(nèi)容則需要1s。此時(shí)揭芍，擁有

個(gè)節(jié)點(diǎn)胳搞，要執(zhí)行

次連接，則需要

次操作称杨，需要31年不眠不休的運(yùn)算肌毅。

算法版本二 QuickUnion

一、在樹(shù)組內(nèi)創(chuàng)建樹(shù)表示連接關(guān)系
數(shù)據(jù)結(jié)構(gòu) 在數(shù)組內(nèi)創(chuàng)建樹(shù)姑原，連接后在同一連接組件的元素悬而，組成一棵樹(shù)。 查找方法 檢查兩個(gè)對(duì)象的根是否相同锭汛。 連接方法 合并兩個(gè)節(jié)點(diǎn)P , Q笨奠，即將Q的Root（根節(jié)點(diǎn)）設(shè)置為P的根節(jié)點(diǎn)。

[圖片上傳中唤殴。般婆。。（6）]上圖中朵逝，3的根節(jié)點(diǎn)可以追溯的9： 3->4->9->9
5的根節(jié)點(diǎn)可以追溯到6: 5->6->6
這個(gè)時(shí)候蔚袍，合并 3 和 5: union(3,5)
把五的根節(jié)點(diǎn)設(shè)置給3的根幾點(diǎn)，也就是修改三的根節(jié)點(diǎn)9為6.

[圖片上傳中配名。啤咽。。（7）]

二渠脉、算法的具體實(shí)現(xiàn)

/快速合并優(yōu)點(diǎn)：連接的時(shí)候時(shí)間復(fù)雜度為N缺點(diǎn)：查找的時(shí)候時(shí)間復(fù)雜度為N(t) */public class QuickUnionUF{private int[] id;public QuickUnionUF(int N){id = new int[N];for (int i = 0; i < N; i++) id[i] = i;}private int root(int i){ //查找樹(shù)的根while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q){ //檢查是否在同一棵樹(shù)內(nèi)return root(p) == root(q);}public void union(int p, int q){ //合并兩棵樹(shù)int i = root(p);int j = root(q);id[i] = j;}}

算法分析
初始化 初始化的時(shí)候宇整，算法需要遍歷整個(gè)數(shù)組，時(shí)間負(fù)載度為

查找在查找操作中芋膘，需要回溯到一棵樹(shù)的根節(jié)點(diǎn)鳞青，程序執(zhí)行效率的時(shí)間復(fù)雜度為常數(shù)

。合并合并操作在這一版本的算法中为朋，需要多次回溯一棵樹(shù)的根節(jié)點(diǎn),時(shí)間復(fù)雜度為

臂拓， t為樹(shù)的高度。 最壞的情況 按照目前的算法潜腻，如果一顆樹(shù)過(guò)于高埃儿，那么尋找root的操作就會(huì)浪費(fèi)大量的時(shí)間器仗。這種算法復(fù)雜度高于版本1融涣。

改進(jìn)版本二垂直化到扁平化
版本二QuickUnion 的缺陷就在于童番，合并操作很容易一不小心就產(chǎn)生一顆非常高的樹(shù)，然后在回溯這棵樹(shù)的時(shí)候威鹿，需要經(jīng)過(guò)大量的節(jié)點(diǎn)才能找到root剃斧，故此效率低下。

第一步：帶權(quán)合并
解決的辦法是降低樹(shù)的高度忽你，在合并操作中幼东，如果碰到兩棵樹(shù)的合并，將小一點(diǎn)的樹(shù)放在大樹(shù)的下面科雳，將小樹(shù)的根節(jié)點(diǎn)作為大樹(shù)的根節(jié)點(diǎn)的子節(jié)點(diǎn)根蟹，則可以降低樹(shù)的高度。因此我們需要一個(gè)額外的數(shù)組來(lái)記錄每一個(gè)樹(shù)的尺寸糟秘。這些值也就被乘坐權(quán)重简逮，改進(jìn)后的算法被稱作帶權(quán)合并。

[圖片上傳中尿赚。散庶。。（8）] 上圖中凌净，如果按照Quick-union的方法悲龟，很有可能得到一顆很高的樹(shù)，原因就在于一顆大樹(shù)的根節(jié)點(diǎn)被當(dāng)作了小樹(shù)的子節(jié)點(diǎn)冰寻。加權(quán)之后须教，進(jìn)行判斷，確保小樹(shù)永遠(yuǎn)被放置在大樹(shù)內(nèi)性雄，大大降低了樹(shù)的高度没卸。

實(shí)現(xiàn)

public class WeightedQuickUnionUF {private int[] id;private int[] sz;//初始化數(shù)組 public WeightedQuickUnionUF(int N) {id = new int[N];sz = new int[N];for (int i = 0; i < N; i++){id[i] = i;sz[i] = 1;//初始化每顆樹(shù)高度都為1 }}private int root(int i) {while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q) {return root(p) == root(q);}public void union(int p, int q) {int i = root(p);int j = root(q);if (i == j) return;//比較樹(shù)的大小，確定讓小樹(shù)追加在大樹(shù)內(nèi)if(sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }else { id[j] = i; sz[i] += sz[j]; }}}

帶權(quán)前后樹(shù)的高度對(duì)比：

[圖片上傳中秒旋。约计。。（9）]

再進(jìn)一步：壓縮路徑
帶權(quán)合并之后樹(shù)的高度明顯降低迁筛，回溯的代價(jià)也就更小了煤蚌。但是，在回溯的時(shí)候我們一就是一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的往上追溯细卧。

[圖片上傳中尉桩。。贪庙。（10）]
在上圖中要找到3的root： 3->4->9 return 9

因?yàn)閕d[4] = 9 如果利用這個(gè)特性蜘犁，在這個(gè)時(shí)候壓縮一下追查的路徑：
3->id[4] return 9

這樣一來(lái)回溯的成本將大大降低，因此可以對(duì)追查root的代碼進(jìn)一步優(yōu)化：

private int root(int i){while (i == id[i]){i = id[id[i]];id[i] = i;}}

效果如下：壓縮素經(jīng)之前：

[圖片上傳中止邮。这橙。奏窑。（11）]壓縮路徑之后：

[圖片上傳中。屈扎。埃唯。（12）]

四種算法時(shí)間復(fù)雜度對(duì)比

[圖片上傳中。鹰晨。墨叛。（13）]

解決實(shí)際問(wèn)題：鄉(xiāng)村公路暢通工程

問(wèn)題描述
某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計(jì)表模蜡，表中列出了每條道路直接連通的城鎮(zhèn)漠趁。省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)城鎮(zhèn)間都可以實(shí)現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過(guò)道路可達(dá)即可）∪碳玻現(xiàn)在要求任意給出兩個(gè)城鎮(zhèn)棚潦，查看其是否連通？

問(wèn)題解決
通過(guò)對(duì)問(wèn)題的建模膝昆，發(fā)現(xiàn)可以直接套用Union-Find算法即可：
編碼實(shí)現(xiàn)：首先創(chuàng)建一個(gè)數(shù)組丸边，包含所有鄉(xiāng)鎮(zhèn)并使其對(duì)應(yīng)一個(gè)編號(hào)，其次使用鄉(xiāng)鎮(zhèn)對(duì)應(yīng)的數(shù)組下標(biāo)創(chuàng)建一個(gè)數(shù)組然后使用連接已經(jīng)連通的鄉(xiāng)鎮(zhèn)荚孵，最后進(jìn)行程序測(cè)試妹窖。

代碼說(shuō)明
代碼實(shí)現(xiàn)，為了方便輸入收叶，這里使用Python來(lái)實(shí)現(xiàn)算法：

-- coding:utf-8 --#這里的鄉(xiāng)鎮(zhèn)僅作演示骄呼，實(shí)際問(wèn)題中可以考慮從文件中讀取PLACES = ['大王村', '河陽(yáng)', '蠻荒殿', '流波鎮(zhèn)', '青云山', '萬(wàn)蝠洞', '鳳凰鎮(zhèn)', '南疆古鎮(zhèn)', '七里侗']#通過(guò)地名獲取編號(hào)def idof(place):return PLACES.index(place)#檢查輸入的地名def cheked(place):return place in PLACES#算法實(shí)現(xiàn)class UnionFind:'''算法的Python實(shí)現(xiàn)，實(shí)際上邏輯是一樣的'''def init(self, N):self.sd = []self.sz = []for i in range(N):self.sd.append(i)self.sz.append(1)def root(self, i):while self.sd[i] != i:i = self.sd[self.sd[i]]self.sd[i] = ireturn idef connected(self, p, q):return self.root(p) == self.root(q)def union(self, p, q):i = self.root(p)j = self.root(q)if i == j:returnif self.sz[i] < self.sz[j]:self.sd[i] = jself.sz[j] += self.sz[i]else:self.sd[j] = iself.sz[i] += self.sz[j]if name == "main":uf = UnionFind(len(PLACES))#隨便連接幾個(gè)點(diǎn)判没，以便于測(cè)試uf.union(idof('大王村'), idof('流波鎮(zhèn)'))uf.union(idof('大王村'), idof('蠻荒殿'))uf.union(idof('流波鎮(zhèn)'), idof('七里侗'))#錄入要查尋的地名place_a = raw_input("請(qǐng)輸入要查詢的第一個(gè)地點(diǎn)：")place_b = raw_input("請(qǐng)輸入要查尋的第二個(gè)地點(diǎn)：")#輸出結(jié)果if cheked(place_a) and cheked(place_b):result = uf.connected(idof(place_a), idof(place_b))print "%s 和 %s 之間是否連通蜓萄？\t %s" % (place_a, place_b, result)else:print "輸入地名有誤"

程序運(yùn)行結(jié)果：

[圖片上傳中。澄峰。嫉沽。（14）] 連通情況：

[圖片上傳中。俏竞。绸硕。（15）]

greenpointan**
** 退出賬號(hào)

當(dāng)前文檔
** 恢復(fù)至上次同步狀態(tài)** 刪除文檔** 導(dǎo)出...** 預(yù)覽文檔** 分享鏈接
系統(tǒng)
** 設(shè)置
 ** 使用說(shuō)明
 ** 快捷幫助
 ** 常見(jiàn)問(wèn)題
 ** 關(guān)于

算法從并查集Union Find算法談算法解決實(shí)際問(wèn)題的過(guò)程

網(wǎng)絡(luò)和大數(shù)據(jù)Tell me about your faimly

GUI程序開(kāi)發(fā)基于面部識(shí)別的日志系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

離散數(shù)學(xué)數(shù)學(xué)史上曾經(jīng)出現(xiàn)過(guò)的三大危機(jī)

歸檔
** 網(wǎng)絡(luò)和大數(shù)據(jù)
** 口語(yǔ)學(xué)習(xí)##算法解決實(shí)際問(wèn)題的一般步驟
Steps to developing a usable algorithm.

問(wèn)題建模（Model the problem.）
尋找算法解決問(wèn)題（Find an algorithm to solve it.）
算法的復(fù)雜度評(píng)判（Fast enough? Fits in memory?）
尋找影響時(shí)間或控件復(fù)雜的的原因（If not, figure out why.）
尋找問(wèn)題源頭（Find a way to address the problem.）
迭代上述過(guò)程，直到算法達(dá)標(biāo)（Iterate until satisfied.）

并查集算法概述

給定一個(gè)包含N個(gè)對(duì)象的集合魂毁，集合中對(duì)象可以相互連接玻佩，實(shí)現(xiàn)如下命令：
Union Union command: 連接兩個(gè)對(duì)象。
Find | Connect Query: 檢查兩個(gè)對(duì)象是否被連接席楚。

上圖經(jīng)歷過(guò)的操作如下：
union(0,1) union(1,2) union(3,4) union(3,8) union(4,9)
union(0,5) union(5,6) union(1,6) union(2,7)
此時(shí)根據(jù)此圖：檢查結(jié)果如下：
True: connected(0,6) True: connected(0,5)
False: connected(2,3) False: connected(6,9)

實(shí)際問(wèn)題引出

如下圖咬崔，P和Q兩個(gè)點(diǎn)之間是否存在一條路徑（P，Q是否連通）烦秩？

在具體一點(diǎn)垮斯，現(xiàn)在要解決的實(shí)際問(wèn)題有如下幾個(gè)：

一張圖片中像素點(diǎn)的連接檢查娶聘。
大型網(wǎng)絡(luò)中設(shè)備之間的連接檢查。查找
社交網(wǎng)絡(luò)中的好友關(guān)系甚脉。
游戲場(chǎng)景中的路徑檢查。

問(wèn)題建模

復(fù)雜問(wèn)題簡(jiǎn)單化
使用整型數(shù)組來(lái)抽象實(shí)際問(wèn)題铆农。舍棄一些細(xì)節(jié)牺氨，僅僅描述其連接關(guān)系。
具體的實(shí)現(xiàn)
使用數(shù)組的下標(biāo)了表示問(wèn)題中的某一個(gè)對(duì)象墩剖，使用對(duì)應(yīng)的值存儲(chǔ)連接參數(shù)猴凹。
進(jìn)一步抽象
A: 連接關(guān)系
如果對(duì)象A和對(duì)象B連接，那么Connected(A,B) 返回True
如果對(duì)象A和對(duì)象B連接岭皂，B又和C連接郊霎，那么Connected(A,C), 返回True
B:連接組件
如果集合{p, q, r, t} 中, p,q,r連接，t和其他三個(gè)不連接爷绘，則有兩個(gè)連接組件：
{p, q, r} 和 {t}

問(wèn)題解決：
創(chuàng)建數(shù)組书劝，使用union方法創(chuàng)建連接組件，使用find/connected方法檢查對(duì)象是否在同一個(gè)連接組件中土至。

算法版本一 QuickFind

通過(guò)問(wèn)題建模购对，確定了數(shù)據(jù)結(jié)構(gòu)和基本方法。解決步驟如下：

一陶因、使用數(shù)組的值表示連接關(guān)系

數(shù)據(jù)結(jié)構(gòu)
創(chuàng)建Int數(shù)組 id[N], 在這個(gè)包含N個(gè)元素的數(shù)組id中骡苞，如果id[p] 和 id[q]的值相同，那么p楷扬，q是連通的解幽。
查找方法
檢查兩個(gè)對(duì)象對(duì)應(yīng)的編號(hào)下的值是否一樣。
連接方法
合并p到q烘苹，修改所有值為id[p]的元素的值為id[q]

befor

union(6,1)

after

二躲株、算法的具體實(shí)現(xiàn)

/* Quick Find 數(shù)據(jù)結(jié)構(gòu)：
 * 優(yōu)點(diǎn)：查找操作比較快,只需要執(zhí)行一次
 * 缺點(diǎn)：合并操作效率慢，可能需要n*n次數(shù)組讀取
 * */
public class QuickFindUF
{
    private int[] id; 
    public QuickFindUF(int N)
    {   
        id = new int[N];
        for (int i = 0; i < N; i++ )
            id[i] = i;
    }   

    //查找：檢查是否連通就是比較兩個(gè)點(diǎn)對(duì)應(yīng)的值
    public boolean connected(int p, int q)
    {   return id[p] == id[q];  }

    //合并：合并的本質(zhì)就是設(shè)置相同的值
    public void union(int p, int q)
    {   
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i > id.length; i++)
            if (id[i] == pid) id[i] = qid;
    }   
}

三镣衡、算法分析

初始化
初始化的時(shí)候徘溢，算法需要遍歷整個(gè)數(shù)組，時(shí)間負(fù)載度為$N$
查找
在查找操作中捆探，僅僅需要訪問(wèn)數(shù)組的兩個(gè)元素即可,程序執(zhí)行效率的時(shí)間復(fù)雜度為常數(shù)$1$然爆。
合并
合并操作在這一版本的算法中，需要遍歷整個(gè)數(shù)組,時(shí)間復(fù)雜度為$N$
最壞的情況
當(dāng)需要連接$N$個(gè)點(diǎn)的時(shí)候黍图，算法需要遍歷數(shù)組$N^{2$次曾雕。當(dāng)前CPU每秒可以執(zhí)行$10}9$條指令;內(nèi)存內(nèi)可以存儲(chǔ)$10^{9$個(gè)字節(jié)的內(nèi)容;讀取內(nèi)存內(nèi)所有內(nèi)容則需要1s。此時(shí)助被，擁有$10}9$個(gè)節(jié)點(diǎn)剖张，要執(zhí)行$10^{9$次連接切诀，則需要$10}9 * 10^9$次操作，需要31年不眠不休的運(yùn)算搔弄。

算法版本二 QuickUnion

一幅虑、在樹(shù)組內(nèi)創(chuàng)建樹(shù)表示連接關(guān)系

數(shù)據(jù)結(jié)構(gòu)
在數(shù)組內(nèi)創(chuàng)建樹(shù)，連接后在同一連接組件的元素顾犹，組成一棵樹(shù)倒庵。
查找方法
檢查兩個(gè)對(duì)象的根是否相同。
連接方法
合并兩個(gè)節(jié)點(diǎn)P , Q炫刷，即將Q的Root（根節(jié)點(diǎn)）設(shè)置為P的根節(jié)點(diǎn)擎宝。

上圖中，3的根節(jié)點(diǎn)可以追溯的9： 3->4->9->9
5的根節(jié)點(diǎn)可以追溯到6: 5->6->6
這個(gè)時(shí)候浑玛，合并 3 和 5: union(3,5)
把五的根節(jié)點(diǎn)設(shè)置給3的根幾點(diǎn)绍申，也就是修改三的根節(jié)點(diǎn)9為6.

二、算法的具體實(shí)現(xiàn)

/*快速合并
 *優(yōu)點(diǎn)：連接的時(shí)候時(shí)間復(fù)雜度為N
 *缺點(diǎn)：查找的時(shí)候時(shí)間復(fù)雜度為N(t)
 * */
public class QuickUnionUF
{

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

    private int root(int i)
    {   //查找樹(shù)的根
        while (i != id[i]) i = id[i];
        return i;
    }   
    
    public boolean connected(int p, int q)
    {   //檢查是否在同一棵樹(shù)內(nèi)
        return root(p) == root(q);
    }   

    public void union(int p, int q)
    {   //合并兩棵樹(shù)
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }   
}

算法分析

初始化
初始化的時(shí)候顾彰，算法需要遍歷整個(gè)數(shù)組极阅，時(shí)間負(fù)載度為$N$
查找
在查找操作中，需要回溯到一棵樹(shù)的根節(jié)點(diǎn)涨享，程序執(zhí)行效率的時(shí)間復(fù)雜度為常數(shù)$1$涂屁。
合并
合并操作在這一版本的算法中，需要多次回溯一棵樹(shù)的根節(jié)點(diǎn),時(shí)間復(fù)雜度為$Nt$灰伟， t為樹(shù)的高度拆又。
最壞的情況
按照目前的算法，如果一顆樹(shù)過(guò)于高栏账，那么尋找root的操作就會(huì)浪費(fèi)大量的時(shí)間帖族。這種算法復(fù)雜度高于版本1。

改進(jìn)版本二垂直化到扁平化

版本二QuickUnion 的缺陷就在于挡爵，合并操作很容易一不小心就產(chǎn)生一顆非常高的樹(shù)竖般，然后在回溯這棵樹(shù)的時(shí)候，需要經(jīng)過(guò)大量的節(jié)點(diǎn)才能找到root茶鹃，故此效率低下涣雕。

第一步：帶權(quán)合并

解決的辦法是降低樹(shù)的高度，在合并操作中闭翩，如果碰到兩棵樹(shù)的合并挣郭，將小一點(diǎn)的樹(shù)放在大樹(shù)的下面，將小樹(shù)的根節(jié)點(diǎn)作為大樹(shù)的根節(jié)點(diǎn)的子節(jié)點(diǎn)疗韵，則可以降低樹(shù)的高度兑障。因此我們需要一個(gè)額外的數(shù)組來(lái)記錄每一個(gè)樹(shù)的尺寸。這些值也就被乘坐權(quán)重，改進(jìn)后的算法被稱作帶權(quán)合并流译。

上圖中逞怨，如果按照Quick-union的方法，很有可能得到一顆很高的樹(shù)福澡，原因就在于一顆大樹(shù)的根節(jié)點(diǎn)被當(dāng)作了小樹(shù)的子節(jié)點(diǎn)叠赦。
加權(quán)之后，進(jìn)行判斷革砸，確保小樹(shù)永遠(yuǎn)被放置在大樹(shù)內(nèi)除秀，大大降低了樹(shù)的高度。

實(shí)現(xiàn)

public class WeightedQuickUnionUF      
{                                   
    private int[] id;                  
    private int[] sz;      
                             
    //初始化數(shù)組       
    public WeightedQuickUnionUF(int N)      
    {                    
        id = new int[N];      
        sz = new int[N];                                                              
        for (int i = 0; i < N; i++)                                                   
        {                   
            id[i] = i;                                                                
            sz[i] = 1;//初始化每顆樹(shù)高度都為1                                                                
        }                                                                             
    }                          
         
    private int root(int i)              
    {                                                                                 
        while (i != id[i]) i = id[i];                                                 
        return i;                                            
    }                                                        
                                                                                      
    public boolean connected(int p, int q)                   
    {                                                        
        return root(p) == root(q);                           
    }                                                 
                                                          
    public void union(int p, int q)                                                   
    {                                                                                 
        int i = root(p);                                                              
        int j = root(q);                                                             
        if (i == j) return;                                                           
        //比較樹(shù)的大小业岁，確定讓小樹(shù)追加在大樹(shù)內(nèi)
        if(sz[i] < sz[j])   { id[i] = j; sz[j] += sz[i]; }                            
        else                { id[j] = i; sz[i] += sz[j]; }                            
    }                                                                                 
}

帶權(quán)前后樹(shù)的高度對(duì)比：

再進(jìn)一步：壓縮路徑

帶權(quán)合并之后樹(shù)的高度明顯降低，回溯的代價(jià)也就更小了寇蚊。但是笔时，在回溯的時(shí)候我們一就是一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的往上追溯。

在上圖中要找到3的root：
3->4->9 return 9

因?yàn)閕d[4] = 9
如果利用這個(gè)特性仗岸，在這個(gè)時(shí)候壓縮一下追查的路徑：

3->id[4] return 9

這樣一來(lái)回溯的成本將大大降低允耿，因此可以對(duì)追查root的代碼進(jìn)一步優(yōu)化：

private int root(int i)
{
    while (i == id[i])
    {
        i = id[id[i]];
        id[i] = i;
    }
}

效果如下：
壓縮路徑之前：

壓縮路徑之后：

四種算法時(shí)間復(fù)雜度對(duì)比

解決實(shí)際問(wèn)題：鄉(xiāng)村公路暢通工程

問(wèn)題描述

某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計(jì)表扒怖，表中列出了每條道路直接連通的城鎮(zhèn)较锡。省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)城鎮(zhèn)間都可以實(shí)現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過(guò)道路可達(dá)即可）〉裂鳎現(xiàn)在要求任意給出兩個(gè)城鎮(zhèn)蚂蕴，查看其是否連通？

問(wèn)題解決

通過(guò)對(duì)問(wèn)題的建模俯邓，發(fā)現(xiàn)可以直接套用Union-Find算法即可：

編碼實(shí)現(xiàn)：
首先創(chuàng)建一個(gè)數(shù)組骡楼，包含所有鄉(xiāng)鎮(zhèn)并使其對(duì)應(yīng)一個(gè)編號(hào)，其次使用鄉(xiāng)鎮(zhèn)對(duì)應(yīng)的數(shù)組下標(biāo)創(chuàng)建一個(gè)數(shù)組
然后使用連接已經(jīng)連通的鄉(xiāng)鎮(zhèn)稽鞭，最后進(jìn)行程序測(cè)試鸟整。

代碼說(shuō)明

代碼實(shí)現(xiàn)，為了方便輸入朦蕴，這里使用Python來(lái)實(shí)現(xiàn)算法：

# -*- coding:utf-8 -*-
#這里的鄉(xiāng)鎮(zhèn)僅作演示篮条，實(shí)際問(wèn)題中可以考慮從文件中讀取
PLACES = ['大王村', '河陽(yáng)', '蠻荒殿', '流波鎮(zhèn)', '青云山', '萬(wàn)蝠洞', '鳳凰鎮(zhèn)', '南疆古鎮(zhèn)', '七里侗']

#通過(guò)地名獲取編號(hào)
def idof(place):
    return PLACES.index(place)

#檢查輸入的地名
def cheked(place):
    return place in PLACES

#算法實(shí)現(xiàn)
class UnionFind:
    '''算法的Python實(shí)現(xiàn)，實(shí)際上邏輯是一樣的'''
    def __init__(self, N): 
        self.sd = []
        self.sz = []
        for i in range(N):
            self.sd.append(i)
            self.sz.append(1)

    def root(self, i): 
        while self.sd[i] != i:
            i = self.sd[self.sd[i]]
            self.sd[i] = i 
        return i

    def connected(self, p, q): 
        return self.root(p) == self.root(q)

    def union(self, p, q): 
        i = self.root(p)
        j = self.root(q)
        if i == j:
            return
        if self.sz[i] < self.sz[j]:
            self.sd[i] = j 
            self.sz[j] += self.sz[i]
        else:
            self.sd[j] = i 
            self.sz[i] += self.sz[j]

if __name__ == "__main__":
    uf = UnionFind(len(PLACES))
    #隨便連接幾個(gè)點(diǎn)吩抓，以便于測(cè)試
    uf.union(idof('大王村'), idof('流波鎮(zhèn)'))
    uf.union(idof('大王村'), idof('蠻荒殿'))
    uf.union(idof('流波鎮(zhèn)'), idof('七里侗'))
    #錄入要查尋的地名
    place_a = raw_input("請(qǐng)輸入要查詢的第一個(gè)地點(diǎn)：")
    place_b = raw_input("請(qǐng)輸入要查尋的第二個(gè)地點(diǎn)：")
    #輸出結(jié)果
    if cheked(place_a) and cheked(place_b):
        result = uf.connected(idof(place_a), idof(place_b))
        print "%s 和 %s 之間是否連通涉茧？\t %s" % (place_a, place_b, result)
    else:
        print "輸入地名有誤"

程序運(yùn)行結(jié)果：

連通情況：

最后編輯于：2017.12.08 01:39:45

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市疹娶，隨后出現(xiàn)的幾起案子降瞳，更是在濱河造成了極大的恐慌，老刑警劉巖，帶你破解...
沈念sama閱讀 217,509評(píng)論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件挣饥，死亡現(xiàn)場(chǎng)離奇詭異除师，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)扔枫，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,806評(píng)論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)汛聚，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人短荐，你說(shuō)我怎么就攤上這事倚舀。” “怎么了忍宋？”我有些...
開(kāi)封第一講書(shū)人閱讀 163,875評(píng)論 0贊 354
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵痕貌，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我糠排，道長(zhǎng)舵稠，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,441評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任入宦，我火速辦了婚禮哺徊，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘乾闰。我一直安慰自己落追，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,488評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布涯肩。她就那樣靜靜地躺著轿钠，像睡著了一般。火紅的嫁衣襯著肌膚如雪病苗。梳的紋絲不亂的頭發(fā)上谣膳，一...
開(kāi)封第一講書(shū)人閱讀 51,365評(píng)論 1贊 302
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音铅乡，去河邊找鬼继谚。笑死，一個(gè)胖子當(dāng)著我的面吹牛阵幸，可吹牛的內(nèi)容都是我干的花履。我是一名探鬼主播，決...
沈念sama閱讀 40,190評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼挚赊，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼诡壁！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起荠割，我...
開(kāi)封第一講書(shū)人閱讀 39,062評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤妹卿，失蹤者是張志新（化名）和其女友劉穎旺矾，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體夺克，經(jīng)...
沈念sama閱讀 45,500評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡箕宙，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,706評(píng)論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了铺纽。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片柬帕。...
茶點(diǎn)故事閱讀 39,834評(píng)論 1贊 347
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖狡门，靈堂內(nèi)的尸體忽然破棺而出陷寝，到底是詐尸還是另有隱情，我是刑警寧澤其馏，帶...
沈念sama閱讀 35,559評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布凤跑，位于F島的核電站，受9級(jí)特大地震影響叛复，放射性物質(zhì)發(fā)生泄漏仔引。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,167評(píng)論 3贊 328
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一致扯、第九天我趴在偏房一處隱蔽的房頂上張望肤寝。院中可真熱鬧当辐，春花似錦抖僵、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,779評(píng)論 0贊 22
一樁弒父案耍群，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至找筝，卻和暖如春蹈垢，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背袖裕。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,912評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工曹抬，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人急鳄。一個(gè)月前我還...
沈念sama閱讀 47,958評(píng)論 2贊 370
代替公主和親
正文我出身青樓谤民，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親疾宏。傳聞我的和親對(duì)象是個(gè)殘疾皇子张足，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,779評(píng)論 2贊 354

從并查集Union Find算法談算法解決實(shí)際問(wèn)題的過(guò)程

并查集算法概述

實(shí)際問(wèn)題引出

問(wèn)題建模

算法版本一 QuickFind

一陶因、使用數(shù)組的值表示連接關(guān)系

二躲株、算法的具體實(shí)現(xiàn)

三镣衡、算法分析

算法版本二 QuickUnion

一幅虑、在樹(shù)組內(nèi)創(chuàng)建樹(shù)表示連接關(guān)系

二、算法的具體實(shí)現(xiàn)

算法分析

改進(jìn)版本二 垂直化到扁平化

第一步：帶權(quán)合并

實(shí)現(xiàn)

再進(jìn)一步：壓縮路徑

四種算法時(shí)間復(fù)雜度對(duì)比

解決實(shí)際問(wèn)題： 鄉(xiāng)村公路暢通工程

問(wèn)題描述

問(wèn)題解決

代碼說(shuō)明

推薦閱讀更多精彩內(nèi)容

改進(jìn)版本二垂直化到扁平化

解決實(shí)際問(wèn)題：鄉(xiāng)村公路暢通工程