媽的，拖延癥發(fā)作，差點沒死掉。。。
動態(tài)連通性問題，有很多的點，我們來可以用union方法在兩個點之間添加鏈接，或者使用connnected方法來判斷兩個點是否相連；
如果一個整數(shù)對pq被認(rèn)為是相連的，那么他有三種性質(zhì)：
1.自反性：p和p是相連的
2.對稱性：如果p和q相連，那么q和p也相連
3.傳遞性，如果p和q向麗娜，且q和r相連，那么p和r就相連。
應(yīng)用：
判斷兩個網(wǎng)絡(luò)是否連通、判斷變量名是否等價、判斷元素是否屬于同一個集合中。等等
算法實現(xiàn)：
1.quick-find算法：
比如有一個數(shù)組
有下面幾種類型0、1、2、3、4、5、6、7、8、9、0；每個數(shù)字代表一種類型
當(dāng)我們要連通這些觸點的時候，我們就遍歷數(shù)組把找到的id[p]全部換位id[q]。
比如要連通 0和1兩個元素：
數(shù)組就變成了1、1、2、3、4、5、6、7、8、9、0。
然后我們連通1和4兩個元素
又變成了4、4、2、3、4、5、6、7、8、9、0
只要我們?nèi)〕鰜淼膇d[p]==id[q]我們就判定他們是連通的
連通部分代碼實現(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)我們要連通兩個p、q節(jié)點的時候，我們就把q節(jié)點的值id[q] = p，
當(dāng)我們使用find(index)的時候，只要 id[index]!=index我們就把index = id[index]并且循環(huán)查找，直到找到id[index]==index為止。就返回這個index。
這種聯(lián)系我們稱為鏈接，這樣我們找到的其實是根觸點，只要根觸點相同，我們就判定p、q是連通的。
代碼實現(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ù)雜程度可能是平方級別的.比如我們總是把1、2、3、4、5觸點連通到第0個觸點上。
這時候我們要用另外一個數(shù)組來保存他的深度，然后總是把深度小的樹加到深度大的樹上。
