不相交集类

简介：

不相交集类是将一些元素合并为不相交的各个集合。在同一个集合中的元素两两等价，不同集合中的元素不等价。

1.等价关系

等价关系必须满足下面三个性质：
(1):自反性，对于集合S中的任意元素a，a R a;(R为定义的关系，比如R为<=， >=等等)
(2);对称性,a R b当且仅当b R a
(3):传递性，若a R b且b R c，则a R c

2.动态等价性问题

集合S中元素a的等价类是集合S的一个子集，该等价类中包含所有与a有等价关系的元素。所以为确定a是否等价b，只需要验证a和b是否属于同一个等价类中。

find操作，它返回包含给定元素的等价类集合的名字。比如：find(a) == find(b),那么a和b处于同一个集合中。

添加操作，如果想添加关系a ~ b，那么首先要判断a和b是否有关系（可以通过find操作验证它们是否在同一个等价类中）。如果a和b不在同一个等价类中，那么要使用求并操作union,这种操作将含有a和b的两个等价类合并为一个等价类。把这种算法称为不相交集合的求并/查找算法。该算法是动态的，因为在算法的执行过程中，集合可以通过union操作而发生改变。

解决动态等价性问题的方案有两种，第一种方案可以保证指令find能够以常数最坏情形运行时间执行，而另一种方案可以保证操作union能够以常数最坏情形运行时间执行。但是两个操作不能同时以常数最坏情形时间执行。

第一种方案：为使find操作快，可以在一个是数组中保存每个元素的等价类的名字。此时find就是简单的O(1)查找。设执union(a,b)，并设a在等价类i中，b在等价类j中，此时我们扫描该数组，将所有的i都改变为j。union的时间复杂度为O(N);

第二种方案：将所有在同一个等价类中的元素放到一个链表中，更新的时候不用搜索整个数组。如果我们还要跟踪每个等价类的大小，并在执行union时将较小的等价类的名字改为较大的等价类的名字。

3.基本数据结构

可以将每个元素都看作是一棵独立的树，每个集合的名字用树根表示，可以用一个数组就可以实现该思路。将所有的元素用一个数组表示，数组每个成员s[i]表示元素i的父亲，如果i是根，那么s[i]=-1；

[cpp] view plaincopy

<embed id="ZeroClipboardMovie_1" src="https://csdnimg.cn/public/highlighter/ZeroClipboard.swf" loop="false" menu="false" quality="best" bgcolor="#ffffff" width="16" height="16" name="ZeroClipboardMovie_1" align="middle" allowscriptaccess="always" allowfullscreen="false" type="application/x-shockwave-flash" pluginspage="http://www.macromedia.com/go/getflashplayer" flashvars="id=1&width=16&height=16" wmode="transparent" style="box-sizing: border-box;">

1. vector<int> s;//存放每个元素的根节点或父节点

对元素x的一次find(x)操作通过返回包含x的树的根而完成。

合并操作union(root1, root2)，将一棵树的父节点链接到另一棵树的根节点合并两棵树。

下面是具体的例子：

初始化元素集合：0,1,2,3,4,5,6,7

image

合并操作union(4,5)，将一棵树的父节点链接到另一棵树的根节点合并两棵树。

image

合并操作union(6，7)，将一棵树的父节点链接到另一棵树的根节点合并两棵树。

image image

4.灵巧求并算法

上面不相交集类中的合并函数是想当随意的，它通过使第二棵树成为第一棵树的子树而完成合并。

第一种改进方法：

对其进行简单的改进是借助任意的方法打破现在的随意性，使得总是较小的树成为较大的树的子树。将这种方法称为按大小求并。

如果不是按大小求并，那么随着合并的进行，某些集合树的深度会增加太多（大于logN)，这意味这find操作的执行时间为O(logN)。

为了实现按大小合并的方法，需要记住每棵树的大小，可以让每个根元素包含它的树的大小的负值。合并的时候首先检查树的大小，将较小的树成为较大树的子树，新的树的大小为两棵树大小的和。

按大小合并的例子步骤：

image image image

第二种改进方法：

按高度求并，它同样保证所有的树的深度最多为O(logN)。我们跟踪每棵树的高度而不是大小并执行合并使得浅的树成为深的树的子树。只有两棵深度相等的树求并的时候树的高度才增加(树的深度加1)。

为了实现按高度求并，需要记住每棵树的高度，可以让每个根元素包含它的树的高度的负值。只有合并的两棵树高度相等的时候才需要更新树的高度(根元素的值减去1）。

按树高度合并的步骤：

image image image

源代码：

/*************************************************************************
    > File Name: DisjointSets.cpp
    > Author: 
    > Mail: 
    > Created Time: 2016年04月25日 星期一 11时22分48秒
 ************************************************************************/

#include <iostream>
#include <vector>
using namespace std;


/********************************************
*    类名称：不相交集合类DisjSets
********************************************/
class DisjSets{
    public:
        explicit DisjSets(int numElements);
        ~DisjSets(){}
        
        int find(int x) const;//查找
        void unionSets(int root1, int root2);//合并
        void unionSetsBySize(int root1, int root2);//按树大小合并
        void unionSetsByHeight(int root1, int root2);//按树高度合并
        void print();//输出各个不相交集合类中元素
    private:
        void print(int x);
    private:
        vector<int> s;//存放每个元素的根节点或父节点
};


/****************************************************************
*   函数名称：DisjSets(int numElements)
*   功能描述: 构造函数,同时对每个元素进行集合初始化
*   参数列表: numElements是集合中元素的个数
*   返回结果：无
*****************************************************************/
DisjSets::DisjSets(int numElements):s(numElements)
{
    for(unsigned i = 0; i < s.size(); ++i)
        s[i] = -1;
}

/****************************************************************
*   函数名称：print(int x)
*   功能描述: 打印元素x
*   参数列表: x是元素的
*   返回结果：void 
*****************************************************************/
void DisjSets::print(int x)
{
    cout << x << " "; 
    for(unsigned i = 0; i < s.size(); ++i){
        if(s[i] == x)
            print(i);
    }
}
/****************************************************************
*   函数名称：print
*   功能描述: 打印集合中的元素
*   参数列表: 无
*   返回结果：void 
*****************************************************************/
void DisjSets::print()
{
    cout << "输出不相交集合类(每行表示一个相交集合): " << endl;
    cout << "s: ";
    for(unsigned i = 0; i < s.size(); ++i)
        cout << s[i] << " ";
    cout << endl;

    for(unsigned i = 0; i < s.size(); ++i){
        if(s[i] < 0){
            print(i);
            cout << endl;
        }
    }
}

/****************************************************************
*   函数名称：find(int x) const
*   功能描述: 查找元素x处于集合的名字
*   参数列表: x是要查找的元素
*   返回结果：返回元素x的集合名字
*****************************************************************/
int DisjSets::find(int x) const
{
    if(s[x] < 0)
        return x;
    else
        return find(s[x]);
}


/****************************************************************
*   函数名称：unionSets(int root1, int root2)
*   功能描述: 合并两个集合
*   参数列表: root1表示集合1，root2表示集合2
*   返回结果：void 
*****************************************************************/
void DisjSets::unionSets(int root1, int root2)
{
    s[root2] = root1; 
}

/****************************************************************
*   函数名称：unionSetsBySize(int root1, int root2)
*   功能描述: 按集合大小合并两个集合,使得较小的树成为较大树的子树
*   参数列表: root1表示集合1，root2表示集合2
*   返回结果：void 
*****************************************************************/
void DisjSets::unionSetsBySize(int root1, int root2)
{
    if(s[root2] < s[root1]){//root2树比较大
        s[root2] += s[root1];//更新树的大小
        s[root1] = root2;//root1的父节点变为root2
    }
    else{
        s[root1] += s[root2];
        s[root2] = root1;
    }
}


/****************************************************************
*   函数名称：unionSetsByHeight(int root1, int root2)
*   功能描述: 按集合高度合并两个集合,使较浅的树成为较深的树的子树
*   参数列表: root1表示集合1，root2表示集合2
*   返回结果：void 
*****************************************************************/
void DisjSets::unionSetsByHeight(int root1, int root2)
{
    if(s[root2] < s[root1]){//root2树比较高
        s[root1] = root2;//直接合并， root1成为root2树的子树 
    }
    else{//root1树比较高，或相等。

         //如果相等则更新树的高度
        if(s[root1] == s[root2])
            s[root1]--;
         s[root2] = root1;
    }   
}


//测试主函数
int main()
{
    cout << "任意合并: " << endl;
    DisjSets disjSets(8);
    disjSets.unionSets(4, 5);
    disjSets.unionSets(6, 7);
    disjSets.unionSets(4, 6);

    disjSets.print();

    cout << "按大小合并: " << endl;
    DisjSets disjSets2(8);
    disjSets2.unionSetsBySize(4, 5);
    disjSets2.unionSetsBySize(6, 7);
    disjSets2.unionSetsBySize(4, 6);
    disjSets2.unionSetsBySize(3, 4);
    disjSets2.print();


    cout << "按高度合并: " << endl;
    DisjSets disjSets3(8);
    disjSets3.unionSetsByHeight(4, 5);
    disjSets3.unionSetsByHeight(6, 7);
    disjSets3.unionSetsByHeight(4, 6);
    disjSets3.unionSetsByHeight(3, 4);
    disjSets3.print();

    return 0;
}

运行结果为：

任意合并: 
输出不相交集合类(每行表示一个相交集合): 
s: -1 -1 -1 -1 -1 4 4 6 
0 
1 
2 
3 
4 5 6 7 
按大小合并: 
输出不相交集合类(每行表示一个相交集合): 
s: -1 -1 -1 4 -5 4 4 6 
0 
1 
2 
4 3 5 6 7 
按高度合并: 
输出不相交集合类(每行表示一个相交集合): 
s: -1 -1 -1 4 -3 4 4 6 
0 
1 
2 
4 3 5 6 7