程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 數據結構與算法——不相交集類的C++實現

數據結構與算法——不相交集類的C++實現

編輯：關於C++

簡介：

不相交集類是將一些元素合並為不相交的各個集合。在同一個集合中的元素兩兩等價，不同集合中的元素不等價。

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；

vector s;//存放每個元素的根節點或父節點

對元素x的一次find(x)操作通過返回包含x的樹的根而完成。 合並操作union(root1, root2)，將一棵樹的父節點鏈接到另一棵樹的根節點合並兩棵樹。

下面是具體的例子：

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

合並操作union(4,5)，將一棵樹的父節點鏈接到另一棵樹的根節點合並兩棵樹。

合並操作union(6，7)，將一棵樹的父節點鏈接到另一棵樹的根節點合並兩棵樹。

4.靈巧求並算法

上面不相交集類中的合並函數是想當隨意的，它通過使第二棵樹成為第一棵樹的子樹而完成合並。 第一種改進方法： 對其進行簡單的改進是借助任意的方法打破現在的隨意性，使得總是較小的樹成為較大的樹的子樹。將這種方法稱為按大小求並。如果不是按大小求並，那麼隨著合並的進行，某些集合樹的深度會增加太多（大於logN)，這意味這find操作的執行時間為O(logN)。為了實現按大小合並的方法，需要記住每棵樹的大小，可以讓每個根元素包含它的樹的大小的負值。合並的時候首先檢查樹的大小，將較小的樹成為較大樹的子樹，新的樹的大小為兩棵樹大小的和。按大小合並的例子步驟：

第二種改進方法： 按高度求並，它同樣保證所有的樹的深度最多為O(logN)。我們跟蹤每棵樹的高度而不是大小並執行合並使得淺的樹成為深的樹的子樹。只有兩棵深度相等的樹求並的時候樹的高度才增加(樹的深度加1)。為了實現按高度求並，需要記住每棵樹的高度，可以讓每個根元素包含它的樹的高度的負值。只有合並的兩棵樹高度相等的時候才需要更新樹的高度(根元素的值減去1）。按樹高度合並的步驟：

5.主要成員函數

        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();//輸出各個不相交集合類中元素

6.主要成員函數介紹

(1)：查找操作find(int x) const，返回該元素所在集合的樹的根。

/****************************************************************
*   函數名稱：find(int x) const
*   功能描述: 查找元素x處於集合的名字
*   參數列表: x是要查找的元素
*   返回結果：返回元素x的集合名字
*****************************************************************/
int DisjSets::find(int x) const
{
    if(s[x] < 0)
        return x;
    else
        return find(s[x]);
}

(2)：任意合並unionSets(int root1, int root2)，將root2樹作為root1的子樹完成合並。

/****************************************************************
*   函數名稱：unionSets(int root1, int root2)
*   功能描述: 合並兩個集合
*   參數列表: root1表示集合1，root2表示集合2
*   返回結果：void 
*****************************************************************/
void DisjSets::unionSets(int root1, int root2)
{
    s[root2] = root1; 
}

(3)：按樹的大小合並unionSetsBySize(int root1, int root2)，使得較小的樹成為較大樹的子樹

/****************************************************************
*   函數名稱：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;
    }
}

(4)：按樹高度合並兩個集合unionSetsByHeight(int root1, int root2),使較淺的樹成為較深的樹的子樹

/****************************************************************
*   函數名稱：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;
    }   
}

7.下面是測試主函數main()

//測試主函數
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;
}

8.下面是不相交集類的源代碼

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

#include 
#include 
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 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