并查集

在计算机科学中,并查集是一种树型的数据结构,其保持着用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个操作用于此数据结构:
Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union:将两个子集合并成同一个集合。
引用自wikipedia并查集

写并查集算法,主要是对“集合”这种数学上的数据结构进行操作。操作有:

  1. 查询操作;
  2. 合并操作。

这两种操作操作的对象是一些集合。但是计算机中难以将“集合”这种数据结构直接表达,我们可以维护许多棵树来当作集合(即并查集森林)。使用树这种数据结构可以让并查集操作复杂度达到最优,水平有限,不做证明。当节点在同一棵树上,认为节点在一个集合内。我们把每棵树的祖先(根)节点作为这个集合的代表。
查询任意两个节点是否属于同一个集合时,我们只需要找到这两个节点的祖先,若相同,则这两个节点在同一棵树上,即在同一个集合内。
我们需要做两个集合的合并操作时,我们只需要找到这两个集合的代表,及这两个集合对应的树的根,将两个根合并即可。合并操作即将其中任意一棵树的根指向另一个根,如何选取哪棵树作为最终的根属于并查集操作的优化。

在做查询或合并操作时,我们需要对并查集进行初始化操作,初始化操作只需要将每个节点的根指向自己:

初始化:

/*CPP code*/
void initialize()
{
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
    }
}

查询操作,及找到当前节点的祖先,可以递归实现:

/*CPP code*/
int find_parent(int i)
{
    if (parent[i] != i)
        return find_parent(parent[i]);
    return i;
}

合并操作,合并a所在的集合与b所在的集合,找到a的祖先与b的祖先,将其合并(将a的根指向b的根):

/*CPP code*/
void union_parent(int a, int b)
{
    parent[find_parent(a)] = find_parent(b);
}

到此,最基本的并查集就结束了。但是!重要的是但是。

同学们一定不会满足于搞懂“最基本”的并查集算法,作为一个程序员应该有的自我修养,应该明白大公司炒鸡bt,任何一点可以优化的细节都不会放过。

并查集操作进行时也有许多可以优化之处,我们从简单的说起。

优化一

减小树的深度

前面说到,我们在构建许多棵树作为并查集森林时,我们仅仅需要知道任意两个节点是否属于同一棵树,而不会在意某一棵树的结构形态。并且我们在查找一个节点的祖先时,我们希望这棵树的深度越小越好,这样我们递归(或者循环)的深度(次数)就会大大减小。
因此,我们在做并查集操作时会想此操作能否尽可能的减小树的深度,最容易想到的就是查找祖先节点的操作,在找一个节点的祖先节点过程中,如果此节点不是祖先节点,那么就把这个节点的根指向祖先节点,最终将此祖先节点返回:

/*CPP code*/
int find_parent(int i)
{
    if (parent[i] != i)
        parent[i] = find_parent(parent[i]);
    return parent[i];
}

优化二

按秩合并

我们使用一棵树来当作集合,尽管我们希望树的深度很小,但是在操作过程中不可避免的会使树的深度增加,这无疑会影响操作速度。但是我们可以尽量平衡每棵树的结构,这棵树“越稳重”,查迅速的相对更快。
所以我们总是希望在合并操作时将一棵更小的树合并到更大的树,这样将不会增加树的深度。但是由于‘优化一’中的路径压缩,一棵树的深的并总是代表这棵树的规模。因此我们引入一个新术语“秩”。
我们在初始化时将每个集合的秩设为0,每次两个秩相同的树合并时,合并后的树的秩加1,如果将秩比较小的树合并到秩比较大的树上,秩不会改变。以下是采用“按秩合并”方法后的初始化操作及合并操作代码:
初始化:

/*CPP code*/
void initialize()
{
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        rank_[i] = 0;
    }
}

合并操作:

/*CPP code*/
void union_parent(int a, int b)
{
    int a_root = find_parent(a);
    int b_root = find_parent(b);
    if (a_root == b_root)
        return;
    if (rank_[a_root] < rank_[b_root])
        parent[a_root] = b_root;
    else if (rank_[a_root] > rank_[b_root])
        parent[b_root] = a_root;
    else
        parent[a_root] = b_root;
        rank_[a_root]++;
}

!!!!!!!!!!!实际上,优化后OJ上提交使用内存竟然多了4KB,时间却一点也没有减少!!!!!!!!!!!!!!!!!!!!!!!!
还真是见鬼了!!!!!!

例题有:

  1. HDU1213:How Many Tables
  2. HDU1232: 畅通工程

Tag: none

Leave a new comment