再说并查集

2015/1/22 posted in  算法&数据结构

上一次写并查集是在看《数据结构》的时候写了树模型的拓展,当时那一章讲到了并查集,并提出了基本的思想。

并查集是我在第一次寒假集训学到的,当时学完写了总结月球美容计划之并查集

今天在看生成树的时候,图论那本书又讲到了并查集。

经过各种资料的查阅,确定并查集并没有特别深入的应用,并查集只不过就是一种判断集合属性的方法,说白了,就是有若干种关系,判断谁和谁是同一种关系。

并查集算法是由3个函数组成的,就三个函数:

初始化函数

根据初始化的不同,并查集有两种写法,这两种写法没有优劣差异,就是初始化不同而已。

初始化为-1

int bc[100];

int UFset1()
{
    for(int i = 0;i < 100;i++)
        bc[i] = -1;
}

初始化为-1是《数据结构》和《图论》都采取的方法,但我学的时候是使用的第二种初始化

初始化为下标

int UFset2()
{
    for(int i = 0;i < 100;i++)
        bc[i] = i;
}

初始化的不同,在剩下两个函数直接造成细节上的差异,但是并没有造成时间复杂度和空间复杂度的差异。

查找函数

查找函数便是用来查找任一元素的根结点(祖先),而在并查集算法中,唯一的优化便是对查找函数的优化。

未优化的查找函数

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    return r;
}

因为并查集数组bc[],存储的是当前结点的父结点,溯流而上,就能找到根结点,找到之后便返回根结点。

对查找函数的优化

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

因为bc数组是记录前驱(父结点)的一棵多叉树,那么如果存在最坏情况(整棵树是线形存在),那么每次查找将最高消耗O(n),也就是说,如果树的深度越低,那么,查找效率越高。因此对其优化、压缩路径。

合并函数

我们可以用查找函数来判断是非属于同一个集合,用合并函数来把两个集合合并成一个集合。

对于合并集合,函数,初始化成什么对其没有影响。

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    bc[fa] = fb;
}

 进一步优化

在图论这本书了提到了一个灰常奇妙的优化。

原理很简单,这个并查集浪费时间在查找上,因为如果树长的很奇葩(线形),那么查找时间将灰常壮观,因此,在查找函数中对其压缩路径,来解决这个问题,那么压缩完路径之后,深度不超过3,那么,查找的时间复杂度解决了,但是还有一个东西浪费时间,就是压缩路径本身。

这样想,如果我们在建树的过程中就尽量让树平衡(相关概念参考:数据结构之二叉树),那么在压缩路径的时候,也会节省一些时间。

至于怎么实现,书中给出的解决方案是靠根结点来记录这个根结点下有多少子节点。

首现,要选择初始化为-1的那种方案,然后对查找进行修改

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (bc[r] >= 0)  //在这里修改了,
        r = bc[r];      //因为如果是根结点,其值为负数而不仅为-1

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

然后对合并函数进行修改:

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    int tmp = bc[fa] + bc[fb];  //结点个数、负数

    if(bc[fa] > bc[fb])    //加权法则
    {
        bc[fa] = fb;
        bc[fb] = tmp;
    }else
    {
        bc[fb] = fa;
        bc[fa] = tmp;
    }
}