算法系列笔记（三）连通

连通是一个重要的概念，连通具有自反性，对称性和传递性。

连通可以用于网络，比如一堆离散的点两两按照输入的数字对连接起来，这样我们就可以通过连通判断任意两点是否连通

连通可以近似为数学集合，一个集合里面都是互相连通的点，所以也可以称这个集合为一个连通块。为了分辨，通常会给集合或连通块一个标识符

可以用江湖门派来解释
比如张三丰、逍遥子、张无忌都是江湖高手，他们就是一个个离散的点，这时候张三丰创立了武当派，逍遥子建立了逍遥派，这时候两个门派其实就两个集合，只不过每一个只有一个元素，而名字武当，逍遥就是他们集合的标识符。这时候张无忌拜师成为张三丰的弟子，张三丰就和张无忌连通，形成一个新的连通块（武当）。

连通通过一个类来实现，包含

• 点的初始化
• 两点的连接 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--;
    }
}