妈的，拖延症发作，差点没死掉。。。
动态连通性问题，有很多的点，我们来可以用union方法在两个点之间添加链接，或者使用connnected方法来判断两个点是否相连；
如果一个整数对pq被认为是相连的，那么他有三种性质：
1.自反性：p和p是相连的
2.对称性：如果p和q相连，那么q和p也相连
3.传递性，如果p和q向丽娜，且q和r相连，那么p和r就相连。
应用：
判断两个网络是否连通、判断变量名是否等价、判断元素是否属于同一个集合中。等等
算法实现：
1.quick-find算法：
比如有一个数组
有下面几种类型0、1、2、3、4、5、6、7、8、9、0；每个数字代表一种类型
当我们要连通这些触点的时候，我们就遍历数组把找到的id[p]全部换位id[q]。
比如要连通 0和1两个元素：
数组就变成了1、1、2、3、4、5、6、7、8、9、0。
然后我们连通1和4两个元素
又变成了4、4、2、3、4、5、6、7、8、9、0
只要我们取出来的id[p]==id[q]我们就判定他们是连通的
连通部分代码实现如下：
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算法
当我们要连通两个p、q节点的时候，我们就把q节点的值id[q] = p，
当我们使用find(index)的时候，只要 id[index]!=index我们就把index = id[index]并且循环查找，直到找到id[index]==index为止。就返回这个index。
这种联系我们称为链接，这样我们找到的其实是根触点，只要根触点相同，我们就判定p、q是连通的。
代码实现：
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.加权quick-union算法
quick-union算法虽然是quick-find的改进，但是在一些情况下复杂程度可能是平方级别的.比如我们总是把1、2、3、4、5触点连通到第0个触点上。
这时候我们要用另外一个数组来保存他的深度，然后总是把深度小的树加到深度大的树上。
网友评论