理解boost::disjoint_sets

Question

我需要使用boost::disjoint_sets，但文档对我来说不太清晰。请有人解释一下每个模板参数的含义，并为创建disjoint_sets给出一个小例子代码吗？

根据要求，我正在使用disjoint_sets来实现Tarjan离线最近公共祖先算法，即-值类型应该是vertex_descriptor。

- Amir Rachum

---

哇，看起来很多人都很好奇，但不知道该如何开始使用它。 - wheaties

在SO上至少有一个使用简单示例：https://dev59.com/blDTa4cB1Zd3GeqPKI0P - Cubbi

已经有人回答了，这会让C++和Boost看起来不好。 :) - Lucas

有人已经回答了这个问题，它在我的SO首页顶部停留着。 :) - kennytm

我几乎不会称之为文档，更像是知识上的自我陶醉。 - lurscher

Answer 1

从文档中我能理解的是：

Disjoint需要为每个元素（在森林树中）关联一个等级和父级。 由于您可能想要处理任何类型的数据，因此您可能不总是想要使用地图来表示父级：对于整数，数组就足够了。 您还需要每个元素的等级（并查集需要等级）。

您需要两个“属性”：

• 一个用于将整数与每个元素相关联（第一个模板参数），即等级
• 一个用于将一个元素与另一个元素相关联（第二个模板参数），即父节点

举个例子：

std::vector<int>  rank (100);
std::vector<int>  parent (100);
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);

为了使用模板中的int*类型，数组应该使用&rank[0], &parent[0]。

如果想要一个更复杂的例子（使用映射），可以查看Ugo的答案。

你只需要给算法提供两个存储数据所需结构（rank/parent）即可。

- Loïc Février

---

如果你不知道元素的最大数量，那么除了 map 之外，是否仍有更简单的解决方案？ - François

@François 是的，有向量属性映射。https://www.boost.org/doc/libs/1_68_0/libs/property_map/doc/vector_property_map.html - MaxPlankton

Answer 2

disjoint_sets<Rank, Parent, FindCompress>

• Rank属性映射用于存储集合的大小（元素 -> std::size_t）。参见按秩合并
• Parent属性映射用于存储元素的父元素（元素 -> 元素）。参见路径压缩
• FindCompress可选参数，定义查找方法。默认为find_with_full_path_compression。请参见此处（默认应该是你需要的）。

示例：

template <typename Rank, typename Parent>
void algo(Rank& r, Parent& p, std::vector<Element>& elements)
{
 boost::disjoint_sets<Rank,Parent> dsets(r, p);
 for (std::vector<Element>::iterator e = elements.begin();
      e != elements.end(); e++)
  dsets.make_set(*e);
  ...
}

int main()
{
  std::vector<Element> elements;
  elements.push_back(Element(...));
  ...

  typedef std::map<Element,std::size_t> rank_t; // => order on Element
  typedef std::map<Element,Element> parent_t;
  rank_t rank_map;
  parent_t parent_map;

  boost::associative_property_map<rank_t>   rank_pmap(rank_map);
  boost::associative_property_map<parent_t> parent_pmap(parent_map);

  algo(rank_pmap, parent_pmap, elements);
}

请注意，“Boost Property Map库包含一些适配器，将实现映射操作的常用数据结构（例如内置数组（指针）、迭代器和std::map）转换为具有属性映射接口的数据结构。”

这些适配器的列表（如boost::associative_property_map）可以在这里找到。

- log0

---

这个可以使用 unordered_map。 - Timmmm

似乎还有一种选项，您无需自己创建rank_map和parent_map。它被称为disjoint_sets_with_storage，如果存储的类型是int，则可以在不进一步指定模板参数的情况下使用。我认为这个是一个很好、简单的例子（它引导了我来到这里）。 - lucidbrot

Answer 3

对于那些无法承受 std::map 开销（或者由于类中没有默认构造函数而无法使用它）但数据不像 int 那么简单的人，我写了 一份指南 ，介绍如何使用 std::vector 进行解决方案，当您事先知道元素总数时，这种方法是相当优秀的。

该指南包含一个 完整可用的示例代码 ，您可以下载并自行测试。

该解决方案假定您控制类的代码，以便您可以添加一些属性。 如果仍然不可能，请始终添加一个包装器：

class Wrapper {
    UntouchableClass const& mInstance;
    size_t dsID;
    size_t dsRank;
    size_t dsParent;
}

此外，如果您知道要素的数量很少，则不需要使用size_t，在这种情况下，您可以为UnsignedInt类型添加一些模板，并在运行时决定将其实例化为uint8_t、uint16_t、uint32_t或uint64_t，您可以使用<cstdint>在C++11中获得它，否则可以使用boost::cstdint。

template <typename UnsignedInt>
class Wrapper {
    UntouchableClass const& mInstance;
    UnsignedInt dsID;
    UnsignedInt dsRank;
    UnsignedInt dsParent;
}

如果你错过了链接，这里是链接：http://janoma.cl/post/using-disjoint-sets-with-a-vector/

- Janoma

---

链接已失效。 - balping

@balping 只有一个链接失效了，指向博客文章。示例代码仍然存在，但您需要花点功夫才能找到它，只需查看存储库历史记录即可。 - Janoma

Answer 4

Loic的答案看起来不错，但我需要初始化父级，以便每个元素都有自己作为父级，所以我使用了函数生成从0开始的递增序列。

使用Boost，并且我导入了bits/stdc++.h并使用using namespace std来简化。

#include <bits/stdc++.h>

#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>
using namespace std;

int main() {
  array<int, 100> rank;
  array<int, 100> parent;

  iota(parent.begin(), parent.end(), 0);
  boost::disjoint_sets<int*, int*> ds(rank.begin(), parent.begin());

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

  cout << ds.find_set(1) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(2) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(3) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(4) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(5) << endl;  // 5
  cout << ds.find_set(6) << endl;  // 6
}

我将 std::vector 更改为 std::array，因为向向量中添加元素会使其重新分配数据，这会使包含的不相交集对象的引用无效。

据我所知，不能保证父节点是特定的数字，所以我写了 1 或 2 或 3 或 4（可以是其中任何一个）。也许文档会更详细地解释哪个数字将被选择为集合的领导者（我还没有研究过）。

在我的情况下，输出为：

2
2
2
2
5
6

看起来很简单，但可能可以改进以使其更健壮（不知道怎么做）。

注意：std::iota 用连续递增的值填充范围[first，last），从value开始重复评估++value。 更多信息：https://en.cppreference.com/w/cpp/algorithm/iota

- Chris Vilches

Answer 5

我之前写了一个简单的实现。看一下吧。

struct DisjointSet {
    vector<int> parent;
    vector<int> size;

    DisjointSet(int maxSize) {
        parent.resize(maxSize);
        size.resize(maxSize);
        for (int i = 0; i < maxSize; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

用法如下。很简单。不是吗？

void solve() {
    int n;
    cin >> n;
    DisjointSet S(n);  // Initializing with maximum Size
    S.union_set(1, 2);
    S.union_set(3, 7);
    int parent = S.find_set(1);  // root of 1
}

- Appaji Chintimi