在C++中实现等价关系(使用boost :: disjoint_sets)

Question

假设您有许多元素,并且需要跟踪它们之间的等价关系.如果元素A等价于元素B,则它等效于所有其他元素B等价.

我正在寻找一种有效的数据结构来编码这些信息.应该可以通过与现有元素的等价来动态添加新元素,并且从该信息中可以有效地计算新元素等效的所有元素.

例如,考虑以下元素[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,似乎满足了我的大多数要求.考虑这个简单的程序,说明如何实现上面的例子:

#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;
}

如上所示,可以有效地添加元素,并动态扩展不相交的集合.如何有效地迭代单个不相交集的元素,而不必迭代所有元素？

Answer 1

很可能你不能这样做，disjoint_sets不支持仅对一组进行迭代。底层的数据结构和算法无论如何都无法有效地做到这一点，即即使内置了disjoint_sets仅对一组集合进行迭代的支持，这也会与迭代所有集合并过滤掉错误的集合一样慢。