我的算法之路 -- Union 并查集


我的算法之路 – Union 并查集

Created by miccall (转载请注明出处)
  • 按理说这类文章首先应该讲一些鸡汤啊 鼓励学习什么的话       但是没有

  • 按理说这类文章应该有一些推荐路径或者学习方法       但是没有

  • 按理说这个文章应该和其他的类似 讲些算法之坑       但是没有

  • 那这篇文章出现的意义是什么 没什么 就是我的学习之路      你爱看就看看

一.连接问题

图片名称

  • 网络节点间的连接状态

  • 用户直接的关系

  • 多媒体 网页 之间的网络关系

  • 实现数学中集合类的实现

  • 路径和连接[图论 更深层的问题]

二.Union 基本操作

1. union(p,q)

  • 把p和q两个元素连接起来

2. find(p)

  • 找到p元素在的那个组

3. isConnected(p,q)

  • 判断p和q是否连接

三.最简单的并查集 Union Find

  • 我们可以用简单的数组来表示并查集关系
node
  • 数组的索引我们可以看作一个元素 那么他们的关系我们怎么确定呢

  • 我们根据他的值 如果相同 我们可以表示他们是有连接关系的

  • 我们暂且给他一个名字 id 意思可以理解为 具有相同id号的元素 他们是互相连接的

node
  • 这个表示 奇数是相互连接的 偶数是互相连接的

  • 下面我们用代码来实现一下这个数据结构

  • 首先我们定义一个类 他有一个数组来表示数据 我们声明一个int指针

  • 第二我们用一个变量来记录他的总数


        class UnionFind
        {
        private:
            int* id ;
            int count ;
        public:
            UnionFind(int n){

            }
            ~UnionFind(){

            }

            //找到这个元素
            int find(int p)
            {

            }

            //判断两个元素是否连接 
            bool isConnected(int p ,int q)
            {

            }

            //连接两个元素
            void unionElements(int p ,int q)
            {

            }
        };
  • 这是我们刚刚分析的基本框架 下面我们一个函数一个函数来讲解

  • 首先是构造和析构 他们要解决的问题就是 构造这个数组和回收这个数组 很好理解

  • 为了让数据独立 我们让他的id都等于他自身 说明自己和自己是相连的 与其他的不相连


        UnionFind(int n){
            count = n ;
            id = new int[n];
            for (int i = 0; i < n; i++)
                id[i] = i;

        }

        ~UnionFind(){
            delete [] id;
        }
  • 我们来写这个find函数 我们传入一个元素p 返回他的id

  • 这样我们就知道 他是属于哪一个组别了 因为实现find特别快 时间复杂度O(1)

  • 所以一般称它为Quick Find


        int find(int p)
        {
            assert(p>=0&& p<count);//保证数据不越界 
            return id[p];
        }
  • 接下来是判断两个元素是否连接

  • 传入两个元素p和q 返回一个bool来判断是否相连

  • 有了上面的理解 这个就很简单了

  • 我们只要分别判断他们的组别 就可以判断他们是否相连了

        bool isConnected(int p ,int q)
        {
            return find(p) == find(q);
        }
  • 最后我们要做的,就是如何把两个元素并到一起呢

  • 我们就要遍历一遍数组 把 第一个元素 的组别赋值给另一个 这样才能实现两个元素的连接

  • 这样的话 时间复杂度为O(n)

  • 我们来写代码加深理解 我们要传入两个元素p和q 来连接他们两个

  • 首先找到他们两个的组别

  • 如果组别相等 说明已经连接在一起了

  • 否则的话 我们来遍历数组

  • 如果我们发现id[i] == pID 那么直接把id[i] = qID; 就好了


        //连接两个元素
        void unionElements(int p ,int q)
        {
            int pID = find(p);
            int qID = find(q);

            if(pID == qID)
                return ;

            for (int i = 0; i < count; i++)
            {
                if(id[i] == pID)
                    id[i] = qID;
            }
        }

四.写测试

  • 如果还没有理顺 那只好用个笨办法啦 那个笔和纸 自己写写了

  • 好了 我们第一个最简单的UnionFind就写完啦

  • 我们把他放到一个 .h 文件中 给他一个namespace 将来方便测试

  • 然后我们再来写一个测试文件 同样放到一个命名空间中

  • 导入第一文件

        namespace UnionFindTestHelper{

            void testUF1( int n ){

                srand( time(NULL) );

                UF1::UnionFind uf = UF1::UnionFind(n);   

                time_t startTime = clock();

                for( int i = 0 ; i < n ; i ++ ){
                    int a = rand()%n;
                    int b = rand()%n;
                    uf.unionElements(a,b);
                }

                for(int i = 0 ; i < n ; i ++ ){
                    int a = rand()%n;
                    int b = rand()%n;
                    uf.isConnected(a,b);
                }

                time_t endTime = clock();

                cout<<"UF1, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
            }
        }
  • 然后我们在主函数中 调用这个test1 我们得到的结果就是 一万的数量级 0.4s

  • 但是我们测试 十万数量级的数据 我们竟然用了 39s的时间 这个效率就非常的慢了

  • 其实我们简单的分析一下就可以直到 我们查找的时候是O(1) 但是连接的时候 就会花费O(n)级别的时间 那我们执行n个数的连接 就会花费O(n^2)级别的时间

  • 这样的话 我们是有必要换个思路去重新实现这个算法了

五.第一次优化 QuickUnion

  • 前面我们讲了如何快速Find 现在我们要将Union提高速度

  • 其实我们这里可以借鉴树的表示思路 把一个元素都看成一个节点 (和树还是有些不同)

node
  • 这里我们简单的有个印象就好了 只要了解他们都有一个指针 是指向他的父亲节点

  • 根节点没有父亲 就指向他自己

  • 我们使用这种思路 会使得Union会非常的快 其实不需要构建树 同样使用数组就可以搞定

node

  • parent[i] 就是他的父亲节点

  • 下面的图 ,新开了一个数组 他们都是独立的节点

图片名称

  • union ( 4 , 3 ) 然后 parent[4] = 3 ;

图片名称

  • union ( 3 , 8 ) 然后 parent[3] = 8 ;

图片名称

  • union ( 6 , 5 ) 然后 parent[6] = 5 ;

图片名称

  • 我们要连接两个数 其中一个已经有父节点了 我们就要循环的找他的根节点

  • 然后把这个数连接到他的根节点上 根节点怎么找呢 我们循环的去找他的父节点

  • 直到parent[i] == i 这样就说明 i这个就是根节点了

  • 那我们如何去看两个数是否连接呢 很简单 就看看他们是不是有共同的根

  • union ( 9, 4 ) 然后 parent[9] = parent[…parent[parent[4]]] ;

图片名称

  • 同样的方法 找2的根节点 和 1的根节点

图片名称

图片名称

图片名称

图片名称

  • 看了这些 我们还是得写代码 来更好的去掌握这种思想

  • 同样的,我们还是用先前的那个架构 我们主要还是改写方法

  • 构造函数和析构函数几乎是没有变化的 只是改了一个名字

        UnionFind(int n){
            count = n ;
            parent = new int[n];
            for (int i = 0; i < n; i++)
                parent[i] = i;

        }

        ~UnionFind(){
            delete [] parent;
        }
  • 查找还是有一点点的不同的 我们要循环 一直找到它的根节点

  • 我们先前讨论过 根节点就是自身指向自身的节点


        //找到这个元素
        int find(int p)
        {
            assert(p>=0&& p<count);
            while(p!=parent[p])//如果p不是根节点 
            {
                p= parent[p]; //就让他指向他的父亲 
            }
            return p;
        }
  • 是否连接函数是没有变化的

  • 我们来看连接操作 说了是快速连接

  • 其实还是很简单的 只要看看他们的根节点 然后让一个元素的指针 指向另一个元素的根节点就可以了

        //连接两个元素
        void unionElements(int p ,int q)
        {
            int pRoot = find(p);
            int qRoot = find(q);

            if(pRoot == qRoot) // 如果已经是连接的就返回 
                return ;

            parent[pRoot] = qRoot ;  //连接两个元素 
        }
  • 我们来继续测试这个算法 一万的数量级 先前的算法用了0.4s 优化后的算法用了0.1s

  • 我们改用十万数据 先前的算法用了40s 优化后的算法用了23s 快了一倍

  • 虽然快了很多 但是以我们的经验来看 23s这个时间 还是不满意的

六.第二次优化 QuickUnion_02

  • 那我么就来继续优化

  • 我们先来分析一下前面这个优化

  • 我们在合并过程中

0201

0202

  • 我们理论上讲 两种情况应该是一样的 但是 我们的代码逻辑会让树变得更高 这样就降低了我们查找的时间

  • 怎么解决这个问题呢 很简单

  • 我们不应该固定的将一个元素的根节点 指向另一个元素的根节点

  • 应该在进行连接的时候 判断一下

  • 具体怎么判断呢 我们重构一下代码 我们可以记录一棵树中有几个元素

  • 每次连接的时候 让少的那个指向那个多的树

  • 这样,更高概率的形成一个层树比较低的树

  • 同样 重构一个算法 架构和之前一样 同样只改写函数

  • 我们用空间换取时间 新开一个数组 来记录这个以i为根的树 有几个节点

  • sz[i] = 1 ; 互相独立的元素 他的节点个数为 1


        UnionFind(int n){
            count = n ;
            sz = new int[n] ;
            parent = new int[n];
            for (int i = 0; i < n; i++)
            {
                parent[i] = i;
                sz[i] = 1 ;
            }    

        }

        ~UnionFind(){
            delete [] parent;
            delete [] sz ;
        }
  • find 和 isConnected 都不需要去维护

  • 我们来看连接操作 其实也特别简单 判断一下sz[i]的个数就行

  • 我们总是将小的那颗树 连接到大的那颗树 然后 sz的总数进行相加

        //连接两个元素
        void unionElements(int p ,int q)
        {
            int pRoot = find(p);
            int qRoot = find(q);

            if(pRoot == qRoot)
                return ;

            if(sz[pRoot]< sz[pRoot])
            {    

                parent[pRoot] = qRoot ;
                sz[qRoot] += sz[pRoot];

            }else{

                parent[qRoot] = pRoot ;
                sz[pRoot] += sz[qRoot];
            }

        }
  • 最后,我们再来测试一下最小的一万数量级 第一个0.4s 第一次优化的0.1s 第二次优化的只用了0.002s 可见提高了不少啊

  • 十万数量级的 我们不比较第一个了 比较第一次和第二次优化的 第一次的用了24s ,第二次的只用了0.03s 之间相差是非常大的

  • 我们在测试更大的数据 一百万的数据量 我们只看第二次优化的 他只用了 0.7s

  • 我们一般的并查集 用到这里就非常不错了

  • 但是还是会有极端的测试数据 会让算法退化

七.第三次优化 rank

0301

  • 上一个算法告诉我们 这样 把节点数少的放到节点数多的下面

0302

  • 直觉告诉我们 这样才是最优的

0303

  • 所以 我们不能根据元素的多少来判断谁连接谁

  • 更准确的是 我们得根据树的层数 来决定谁连接谁

  • 基于rank的优化 rank[i] 表示根节点为i的树的高度

  • 同样 重构代码 我们还是只写函数

  • 改一个名字 使他更具有意义 (改哪里?自己看)

        UnionFind(int n){
            count = n ;
            rank = new int[n] ;
            parent = new int[n];
            for (int i = 0; i < n; i++)
            {
                parent[i] = i;
                rank[i] = 1;
            }    

        }
        ~UnionFind(){
            delete [] parent;
            delete [] rank ;
        }
  • 同样 find 和 isConnected 都不需要去维护

  • 只看连接操作 当层数不一样的时候 我们是不去维护这个树的高度的

  • 当rank[qRoot] == rank[pRoot] 的情况下 parent[pRoot] = qRoot

  • 我们才来维护 rank[qRoot] += 1

  • 原本在第一层的 qRoot 到了第二层 所以就要加上 1

        //连接两个元素
        void unionElements(int p ,int q)
        {
            int pRoot = find(p);
            int qRoot = find(q);

            if(pRoot == qRoot)
                return ;

            if(rank[pRoot]< rank[pRoot])
            {    
                parent[pRoot] = qRoot ;
            }
            else if(rank[qRoot]< rank[pRoot])
            {
                parent[qRoot] = pRoot ;
            }
            else{

                parent[pRoot] = qRoot ;
                rank[qRoot] += 1 ;
            }

        }
  • 测试呢 百万数据用了 0.7s 可能优化并不明显 是因为 这样的情况并不多见

  • 甚至有些时候 会比上一个算法要慢那么一点点

  • 但是还是推荐用这个方法的

八.第四次优化 路径压缩 Path Compression

  • 我们刚刚优化了很多Union操作,回过头来 想一下find操作 也是还可以优化的

001

  • 我们找他的根节点的时候 不断地找他的parent节点 这个时候 可以看成 我们把这个数组全部遍历了一次

  • 我们其实可以用一种方法 来减少这个遍历节点个数 比如说 我们执行 find(4)

  • 4 的 parent 不是他自己 说明4不是根节点 我们要继续向上找 这时 我们可以让 4 连接到他父亲的父亲 这样 这个树就变矮了

002

  • 那假如说 他的父亲就是根节点呢 那也没关系 因为根的父亲还是他自己 那就直接连到根节点了 是不会遇到无效的情况的

  • 那么下一步 我们要找的就是 find(2) 了 这样 我们就实现了路径压缩 跳过了 3 这个节点

  • 同样的 我们考察 2 的时候 也使用这个方法

003

  • 这样 我们又跳了一个节点 我们很快的找到了他的根节点

  • 这个树的层数就大大减少了

  • 其实原理讲了这么多 代码写起来 也就一行代码的事 同样 我们只给出find的写法 其他的保持不变


        int find(int p)
        {
            assert(p>=0 && p<count);
            while(p!=parent[p])
            {
                parent[p] = parent[pRoot[p]];
                p = parent[p] ;
            }

            return p ;
        }
  • 这样,我们来测试一下 直接使用一百万的数据 没有使用路径压缩的rank方法 使用了0.7s 的时间

  • 而我们优化之后 使用了0.5s的时间 性能上是有所提升的

  • 那我们的问题又来了 这是最优的解吗 直觉告诉我们 不是 最优的应该化成这样的形式

004

  • 其实我们是可以做到的 只是比较绕一些

  • 我们要写一个递归函数来实现

  • 我们知道 find(x) 返回的 就是x节点所在树的根节点

  • 那我们就好理解了 就让 x的parent 直接指向 find(x) 返回的结果就可以了

  • find(x) 的结果也是 find(parent[x]) 的结果 这两者的根是一样的

  • 这样一直递归 我们就可以一直连上父亲节点的结果


        //找到这个元素
        int find(int p)
        {
            assert(p>=0&& p<count);

            if( p != parent[p] )
                parent[p] = find( parent[p] );

            return parent[p] ;
        }
  • 这样的话 我们还可以再测试一下 其实 这样的写法 时间上会稍微慢那么一点点 可想而知 时间是递归所消耗的时间
    总结 : 并查集的操作 时间复杂度 近乎  是 O(1) 的