@PandoraKey 2022-11-08T11:35:48.000000Z 字数 5042 阅读 37

由一场迷宫游戏引发的算法思考

并查集

五一放假回家的那几日小假，赋闲在家，还在读幼儿园的小表弟就喜欢抱着一堆旧报纸来找我玩，看见一张超大的迷宫图，要我给他找出能把红色两点相连通的路径来，这个工程量着实让我吃了一惊，但好在勾勾画画之后找出了这条蜿蜒曲折的连通路径。

回家后我就在想，万一哪天面试的时候给我来一张比这迷宫还大几十倍，甚至几百倍的超大型迷宫，还是让我求给定两点之间是否存在通路，那我岂不是面试要黄喽？心中暗自揣摩之下，兜兜转转找到了union-find，也就是并查集，这个算法可以解决动态连通问题，这可帮了我大忙，感觉就想吃下了一颗定心丸。

好，我们开始这次的知识分享，首先并查集是什么，我卖个关子，暂时不说它的定义，咱们先从连通分量开始，比如说现在有

$\left\{0,1,2,3,4,5,6,7,8,9\right\}$ 这么十个数字，同时我们也有两种操作，一个是连接两个元素的操作

$union()$ ，以及判断两个元素之间是否存在通路的操作

$isHaveway()$ 。

假设说我们现在有一个数组 $A$

0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9

上面是数组固定的 index 值，也就代表着我们集合 $A$ 中的元素；下面一排是 index 所指向的数值，初始时与 index 值相等，即指向其本身。此时我们执行 $union(1,2)$ 操作，也就意味着要修改 index =1 和 index=2 的数值，将其变更为 1 ，这样子元素 1 与 2 就连接起来了。

0	1	2	3	4	5	6	7	8	9
0	1	1	3	4	5	6	7	8	9

然后紧接着继续操作 $union(4,5)$ ，同理也是修改 index=4 和 index=5 的数值，将其变更为 4 ，这样子 4 和 5 就连接起来了。

0	1	2	3	4	5	6	7	8	9
0	1	1	3	4	4	6	7	8	9

至此 1 和 2 ，4 和 5 连接起来了，然后执行操作 $union(2,4)$ ，这个时候的连接是属于两个连通分量集合之间的连接【做个说明：单个元素可以称作连通分量，在这个例子中，为了表示区别，我把包含多个元素的连通分量称作是连通分量集合，单个则是连通分量】。这次两个连通分量集合的连接与单个连通分量之间的连接的原理是一样的，修改 index=2 和 index=4 的数值，并将 index=2 与 index=4 这个索引值的对应数值取出，假设称其为 $value_2$ 与 $value_4$ 然后不断地遍历比较，如果有数值与 $value_4$ 相等的，就将其修改为 $value_2$ 。

0	1	2	3	4	5	6	7	8	9
0	1	1	3	1	1	6	7	8	9

就是这样，我们多进行几次 $union()$ 操作，让数组变成下面这样：

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	0	0	0	1

它所表示的连通图如下：

图一：数组对应的连通图

好，上面已经把 $union()$ 操作讲的非常详细了，现在我们继续讲解下一个操作 $isHaveWay()$ 。

这个操作的原理很明确，就是要判断两个给定元素所对应的数值是否相等，如果相等就返回存在通路，如果不等，就返回没有通路。

现在我们给出这两个操作的完整代码，当然，这次使用 $Java$ 作为编程语言。

Java 示例：

class getCollection{
    private int array[];
    getCollection(int n){
        array = new int[n];
        for(int i=0;i<n;i++){
            array[i]=i;
        }
    }
    public void union(int p,int q){
        int pVal=array[p];
        int qVal=array[q];
        for(int i=0;i<array.length;i++){
            if(array[i]==qVal){
                array[i]=pVal;
            }
        }
    }
    public void isHaveWay(int p, int q) {
        if(array[p]==array[q]){
            System.out.println("true");
        }else{
            System.out.println("false");
        }
    }
    public void show(){
        for(int i=0;i<array.length;i++){
            System.out.print(i);
        }
        System.out.println();
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}

其中的 $show()$ 是为了让输出可视化，更加方便读者了解其中的数值变化而编写的方法。

以上就是使用数组开发的并查集，我们来分析一下这个算法的时间开销。

从代码中我们可以得到以下信息：

getCollection()	union()	isHaveWay()
$N$	$N^2$	$1$

事实上只有判断两个元素之间是否存在通路是属于常数时间开销，这个结果是令人满意的，但是在执行合并操作的时候，这个时间开销有可能存在平方时间，当我们要对 $N$ 个元素进行 $N$ 次合并操作的时候，时间开销就会变成平方时间了，这是噩梦一般的时间复杂度，所以我们必须想办法改进它。

这里开始讨论一种建树的方法来改良合并操作。其基本思想是将元素看作是一个节点，不断地与想要连接的其他节点建立父子关系，这里把这种连接方法命名为 $fast_union()$ ，与上面的合并操作做个区分，我们来看看它是如何实现的。

首先是初始化这个元素集合，同样是 $0\sim9$ ，接着执行操作：

$fast\_union(5,3);$
$fast\_union(3,1);$
$fast\_union(9,7);$
$fast\_union(7,1);$
$fast\_union(4,2);$
$fast\_union(2,0);$
$fast\_union(8,6);$
$fast\_union(6,0);$

好，现在我们得到了两个较大的连通分量集合 $\left\{1,3,5,7,9\right\}$ 与 $\left\{0,2,4,6,8\right\}$ ，它们之间的联系如下：

0	1	2	3	4	5	6	7	8	9
0	1	0	1	2	3	0	1	6	7

这个时候执行 $fast\_union(5,4)$ ，先不说结果如何，我们来一起分析算法的走向：

先是找到 $5$ 这个元素的根节点 $root_5$ 【根节点的寻找方法很简单，只要当 index 值和相对应的数组里面存放的值相等时，它便是根节点】嗯，往上一直找，
$5——>3——>1——>1$ 好！数值对应相等！ 1 就是 5 的根节点。同理，接着寻找 4 的根节点，
$4——>2——>0——>0$ 数值对应相等！ 0 就是 4 的根节点。
修改 index=1 的对应数值，将其调整为 0 ，这样就将两棵树合并在一起了，并且每个点之间也都互相连通，构成一个大的连通集合 $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ 。

上面采用建树的方式来改进合并操作的代码实现是很容易的，我们来看看代码，然后对算法进行分析。

Java 示例：

class treeCollect{
    private int treeArray[];
    treeCollect(int n){             //初始化整个建树数组
        treeArray=new int[n];
        for(int i=0;i<n;i++){
            treeArray[i]=i;
        }
    }
    public int root(int element){   //查询根节点，原理同上文的第①点的备注解释
        while(element!=treeArray[element]){
            element=treeArray[element];
        }
        return element;
    }
    public void isHaveWay(int p,int q){     //判断两点之间是否存在通路，只需要判断两点的根节点是否一致即可
        if(root(p)==root(q)){
            System.out.println("true");
        }else{
            System.out.println("false");
        }
    }
    public void fast_union(int p,int q){    //连接两点，原理同第①点
        int i=root(p);
        int j=root(q);
        treeArray[i]=j;
    }
    public void show(){     //show一下，可视化结果
        for(int i=0;i<treeArray.length;i++){
            System.out.print(i);
        }
        System.out.println();
        for(int i=0;i<treeArray.length;i++){
            System.out.print(treeArray[i]);
        }
        System.out.println();
    }
}

最后我写了个测试执行 $fast\_union(5,4)$ ，运行 $isHaveWay(9,8)$ 达到了预期效果：

预期效果图

整棵树的构形如下：

整棵树的构形

现在分析一下这个算法的时间开销：

getCollection()	union()	isHaveWay()
$N$	$N$	$N$

可以看见上述算法的优势在于合并的时候变快了，但是存在另外一种慢，是在判断两点之间是否存在通路的时候，可能需要回溯的树的节点太多了，因为可能会存在一长串的瘦长的树，这样子回溯起来的时间开销就会变得非常的大，这样子就又不是优雅的算法实现了。

行吧，再来想想有没有什么办法可以解决这个问题？嗯…带权能否解决呢？是的，没错就是带权，它的思想其实说破之后就很简单，按照我的理解是这样的，有俩树，一大一小，为了保证我们合并之后的超大树变得树深没有很大，那我们就把小树放在大树下面，而不是把大树放在小树下面，举个例子帮助理解，比如说现在有两棵树，一棵树深是四，一棵是二，这个时候如果把树四放在树二下面，也就是说将树四的根节点与树二的根节点连接起来，这样树深就变成五；相反如果把树二放在树四下面，也就是把树二的根节点和树四的根节点连接起来，树深就还是四，并没有变化。只有当 $Tree_1$ 的树深大于或者等于 $Tree_2$ 的树深时，合并之后的树深才会加一，否则不会变化。这就是带权的动态连通的整体思想了。

我们来看下代码实现，跟上面的代码一样，只是多出一个数组用于存放对应根节点下有多少个元素，并对 $fast\_union()$ 方法做出修改，将其该更改为 $fast\_union\_weight()$ 。

Java 示例：

class treeCollect_weight{
    private int treeArray[];
    private int rootNode[];
    treeCollect(int n){             //初始化整个建树数组与将当前index值视为根节点元素的个数的数组
        treeArray=new int[n];
        rootNode=new int[n];
        for(int i=0;i<n;i++){
            treeArray[i]=i;
            rootNode[i]=i;
        }
    }
    public int root(int element){   
        while(element!=treeArray[element]){
            element=treeArray[element];
        }
        return element;
    }
    public void isHaveWay(int p,int q){     //判断两点之间是否存在通路，只需要判断两点的根节点是否一致即可
        if(root(p)==root(q)){
            System.out.println("true");
        }else{
            System.out.println("false");
        }
    }
    public void fast_union_weight(int p,int q){    
        int i=root(p);
        int j=root(q);
        //以下是修改的部分
        if(i==j){System.out.println("该两元素已连接");}
        if(rootNode[i]<rootNode[j]){
            treeArray[i]=j;
            rootNode[j]=rootNode[i]+rootNode[j];
        }else{
            treeArray[j]=i;
            rootNode[i]=rootNode[j]+rootNode[i];
        }
    }
}

上述代码中的合并操作的时间开销就已经达到了 $O(lgN)$ ，每当看到对数时间的算法，总是让人心情舒畅。

当然还可以继续优化，比如说带权的路径压缩。只需要加入一行代码即可使得树深较大的树在，也就是在查询根节点的时候呢，把孩子节点指向的父亲节点更换成指向祖父节点即可。

Java 示例：

public int root(int element){   
        while(element!=treeArray[element]){
            treeArray[element]=treeArray[treeArray[element]];
            element=treeArray[element];
        }
        return element;
    }

这样子就可以基本展平了。

由一场迷宫游戏引发的算法思考

内容目录