算法系列笔记（三）连通
连通是一个重要的概念，连通具有自反性，对称性和传递性。
连通可以用于网络，比如一堆离散的点两两按照输入的数字对连接起来，这样我们就可以通过连通判断任意两点是否连通
连通可以近似为数学集合，一个集合里面都是互相连通的点，所以也可以称这个集合为一个连通块。为了分辨，通常会给集合或连通块一个标识符
可以用江湖门派来解释
比如张三丰、逍遥子、张无忌都是江湖高手，他们就是一个个离散的点，这时候张三丰创立了武当派，逍遥子建立了逍遥派，这时候两个门派其实就两个集合，只不过每一个只有一个元素，而名字武当，逍遥就是他们集合的标识符。这时候张无忌拜师成为张三丰的弟子，张三丰就和张无忌连通，形成一个新的连通块（武当）。
连通通过一个类来实现，包含
- 点的初始化
- 两点的连接 union
- 判断一个元素所属集合的标识符 find
- 返回连通块的数量 count
Quick_find
public class Union_find {
private int [] id; //id序号代表点的序号，id[]的值代表该点所属的集合标识
private int count; //连通块的数目
public Union_find(int n) {
count=n;
id=new int[n];
for(int i=0;i<n;i++) {
id[i]=i; //一开始每一个点都变成一个孤立的连通块
}
}
public int count() {
return count;
}
public boolean connected(int a,int b) { //判断a,b是否连通
return find(a)==find(b);
}
public int find (int a) { //返回a所属集合标识
return id[a];
}
public void union(int a,int b) {
int aid=find(a);
int bid=find(b);
if(aid==bid) return;
for(int i=0;i<id.length;i++) { //这里要遍历所有的aid相同的所有元素要他们统一归顺于bid集合
if(id[i]==aid)
id[i]=bid;
}
count--;
}
}
这种称之为quick-find方法，原因是find很简单粗暴，直接找相应数组值即可，但是union很麻烦因为要遍历数组，速度很慢。
这里的union方法按照江湖解释就是，门派B决定吸收门派A的人，希望A的全体成员都要加入B门派。但是由于A门派是很离散的组织，每个人都各自修炼没有联系，要让所有人加入B门派，要一个个去询问成员的意见，让他们加入B门派
Quick_union实现
public class Union_find2 {
private int [] id;
private int count;
public Union_find2(int n) {
count=n;
id=new int[n];
for(int i=0;i<n;i++) {
id[i]=i;
}
}
public int count() {
return count;
}
public boolean connected(int a,int b) {
return findroot(a)==findroot(b);
}
public int findroot (int a) {
while(a!=id[a]) a=id[a];
return a;
}
public void union(int a,int b) {
int aroot=findroot(a);
int broot=findroot(b);
if(aroot==broot) return;
id[aroot]=broot;
count--;
}
}
这里大同小异就是find变成findroot,什么叫findroot这里又要用江湖之人来解释了。
在这种实现方式中，门派之间都是等级分明，每个人都有明确的师傅和徒弟关系，而且一个大门派只有一个祖师爷。所谓的通过findroot来分辨门派，其实就是找到那个弟子的师父的师父的师父......最终找到祖师爷，而通过这个祖师爷就能识别出这是哪个门派的。
findroot中
while(a!=id[a]) a=id[a];就是找祖师爷，直到找到一个人的师父是自己（假设祖师爷都是自学成才的哈）
然后union的时候，只需要让祖师爷投靠另外一个祖师爷，那么他旗下的所有弟子当然是乖乖听话归顺啦。
加权quick_union
加权quick_union在quick_union基础上做出了改进，做出了什么改进呢？有请灵魂画手
111.png
我们之前讲的江湖门派等级其实等价于一颗树的结构，祖师爷其实就是树顶。树顶的连接其实就是门派合并。现在有A1和A2两棵树，明显A2高。这幅图我是将两幅图合并在一起，看的时候只看一个A1和A2。可以看出A1和A2有两种连接方式。P1和P2，P1代表A1连接到A2，P2代表A2连接到A1。
对于P1连接意味着A1中所有节点在find的时候都多了一个节点（A2顶部）的搜寻。
对于P2连接意味着A2中所有节点在find的时候都多了一个节点（A1顶部）的搜寻。
明显P2连接受影响的点更多，这样连接成本消耗（大概率，因为具体情况要看输入）会更大。从树的高度也可直观反映。所以尽量P1连接会更好。
避免P2实现P1连接，就成为加权quick_union存在的意义，为了衡量树的高低，需要加上数组sz来代表树的子节点有多少个（江湖师父的小弟有几个）。
下面为代码实现
public class WeightedUnion_find {
private int count;
private int []id;
private int []sz; //代表树的节点数/弟子数
public WeightedUnion_find(int n) {
id=new int[n];
count=n;
for(int i=0;i<n;i++) {
id[i]=i;
sz[i]=1;
}
}
public int getcount() {
return count;
}
public boolean connected(int a,int b) {
return findroot(a)==findroot(b);
}
public int findroot(int a) {
while(a!=id[a]) {
a=id[a];
}
return a;
}
public void union(int a,int b) {
int aroot=findroot(a);
int broot=findroot(b);
if(aroot==broot) {
return ;
}
if(sz[a]<sz[b]) {
id[a]=id[b];
sz[b]+=sz[a]; //b的节点数合并a的节点数，a节点数不变
}
else {
id[b]=id[a];
sz[a]+=sz[b];
}
count--;
}
}
