媽的旺入，拖延癥發(fā)作兑凿，差點(diǎn)沒(méi)死掉凯力。。礼华。
動(dòng)態(tài)連通性問(wèn)題咐鹤，有很多的點(diǎn)，我們來(lái)可以用union方法在兩個(gè)點(diǎn)之間添加鏈接圣絮，或者使用connnected方法來(lái)判斷兩個(gè)點(diǎn)是否相連祈惶；
如果一個(gè)整數(shù)對(duì)pq被認(rèn)為是相連的，那么他有三種性質(zhì)：
1.自反性：p和p是相連的
2.對(duì)稱性：如果p和q相連晨雳，那么q和p也相連
3.傳遞性行瑞，如果p和q向麗娜，且q和r相連餐禁，那么p和r就相連。
應(yīng)用：
判斷兩個(gè)網(wǎng)絡(luò)是否連通突照、判斷變量名是否等價(jià)帮非、判斷元素是否屬于同一個(gè)集合中。等等
算法實(shí)現(xiàn)：
1.quick-find算法：
比如有一個(gè)數(shù)組
有下面幾種類型0讹蘑、1末盔、2、3座慰、4陨舱、5、6版仔、7游盲、8、9蛮粮、0益缎；每個(gè)數(shù)字代表一種類型
當(dāng)我們要連通這些觸點(diǎn)的時(shí)候，我們就遍歷數(shù)組把找到的id[p]全部換位id[q]然想。
比如要連通 0和1兩個(gè)元素：
數(shù)組就變成了1莺奔、1、2变泄、3令哟、4、5妨蛹、6屏富、7、8滑燃、9役听、0。
然后我們連通1和4兩個(gè)元素
又變成了4、4典予、2甜滨、3、4瘤袖、5衣摩、6、7捂敌、8艾扮、9、0
只要我們?nèi)〕鰜?lái)的id[p]==id[q]我們就判定他們是連通的
連通部分代碼實(shí)現(xiàn)如下：
public void union(int p, int q){
? ? int pID= find(p);
? ? int qID = find(q);
? ? if(pID == qID ) return;
? ? for(int i=0;i<id.length;i++){
? ? ? if(id[i]==pID) id[i] = qID;
? ? }
? ? count--;
}
public int find(int index){
? ? return id[index];
}
2.quick-union算法
當(dāng)我們要連通兩個(gè)p占婉、q節(jié)點(diǎn)的時(shí)候泡嘴，我們就把q節(jié)點(diǎn)的值id[q] = p，
當(dāng)我們使用find(index)的時(shí)候逆济，只要 id[index]!=index我們就把index = id[index]并且循環(huán)查找酌予，直到找到id[index]==index為止。就返回這個(gè)index奖慌。
這種聯(lián)系我們稱為鏈接抛虫，這樣我們找到的其實(shí)是根觸點(diǎn)，只要根觸點(diǎn)相同简僧，我們就判定p建椰、q是連通的。
代碼實(shí)現(xiàn)：
private int find(int p){
? ? while(p!=id[p]) p = id[p];
? ? return p;
}
public void union(int p ,int q){
? ? int pRoot = find(p);
? ? int qRoot = find(q);
? ? if(pRoot) == qRoot) return;
? ? id[pRoot] = qRoot;
? ? count--;
} ? ?
3.加權(quán)quick-union算法
quick-union算法雖然是quick-find的改進(jìn)岛马，但是在一些情況下復(fù)雜程度可能是平方級(jí)別的.比如我們總是把1棉姐、2、3蛛枚、4谅海、5觸點(diǎn)連通到第0個(gè)觸點(diǎn)上。
這時(shí)候我們要用另外一個(gè)數(shù)組來(lái)保存他的深度蹦浦，然后總是把深度小的樹(shù)加到深度大的樹(shù)上扭吁。
