在C++中實現等價關係（使用boost :: disjoint_sets）

假設您有很多元素，並且需要跟蹤它們之間的等價關係。如果元素A等同於元素B，則它等同於B相當於的所有其他元素。在C++中實現等價關係（使用boost :: disjoint_sets）

我正在尋找一個高效的數據結構來編碼這些信息。應該可以通過與現有元素的等價性動態地添加新元素，並且應該可以從該信息有效地計算新元素等同的所有元素。

例如，考慮下面的同值集合中的元素的[0,1,2,3,4]：

0 = 1 = 2 
3 = 4

其中等號表示等價。現在我們添加一個新的元素5

0 = 1 = 2 
3 = 4 
5

和執行等價5=3，數據結構變得

0 = 1 = 2 
3 = 4 = 5

由此看來，一個人應該能夠通過任何元素設置的等價有效迭代。對於5，這個集合將是[3,4,5]。

Boost已經提供了一個方便的數據結構，稱爲disjoint_sets，似乎滿足了我的大部分要求。考慮這個簡單的程序，illustates如何實現上面的例子：

#include <cstdio> 
#include <vector> 
#include <boost/pending/disjoint_sets.hpp> 
#include <boost/unordered/unordered_set.hpp> 

/* 
    Equivalence relations 
    0 = 1 = 2 
    3 = 4 
*/ 

int main(int , char* []) 
{ 
    typedef std::vector<int> VecInt; 
    typedef boost::unordered_set<int> SetInt; 

    VecInt rank (100); 
    VecInt parent (100); 
    boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]); 
    SetInt elements; 
    for (int i=0; i<5; ++i) { 
     ds.make_set(i); 
     elements.insert(i); 
    } 

    ds.union_set(0,1); 
    ds.union_set(1,2); 
    ds.union_set(3,4); 

    printf("Number of sets:\n\t%d\n", (int)ds.count_sets(elements.begin(), elements.end())); 

    // normalize set so that parent is always the smallest number 
    ds.normalize_sets(elements.begin(), elements.end()); 
    for (SetInt::const_iterator i = elements.begin(); i != elements.end(); ++i) { 
     printf("%d %d\n", *i, ds.find_set(*i)); 
    } 

    return 0; 
}

如所看到的上述一個能有效添加元素，並動態地展開不相交的集合。如何有效地迭代單個不相交集的元素，而不必遍歷所有元素？

來源

2010-09-17 dzhelil

很可能你不能這樣做，disjoint_sets不支持只對一組進行迭代。底層的數據結構和算法無論如何都無法有效地完成它，即使只有一個集合支持內置於disjoint_sets的迭代，這對迭代所有集合來說也是一樣慢，並且濾除了錯誤集。

來源

2010-11-09 15:53:30 pts

在C++中實現等價關係（使用boost :: disjoint_sets）

回答

相關問題