理解 boost::disjoint_sets

问题描述

我需要使用 boost::disjoint_sets，但文档是我不清楚.有人能解释一下每个模板参数的含义吗，或者给出一个创建 disjoint_sets 的小示例代码?

I need to use boost::disjoint_sets, but the documentation is unclear to me. Can someone please explain what each template parameter means, and perhaps give a small example code for creating a disjoint_sets?

根据要求，我使用 disjoint_sets 来实现 Tarjan 的离线最不常见祖先算法, 即 - 值类型应为 vertex_descriptor.

As per the request, I am using disjoint_sets to implement Tarjan's off-line least common ancestors algorithm, i.e - the value type should be vertex_descriptor.

推荐答案

我能从文档中了解到什么:

What I can understand from the documentation :

Disjoint 需要将等级和父级(在森林树中)与每个元素相关联.例如，由于您可能想要处理任何类型的数据，因此您可能并不总是想要为父级使用映射:使用整数数组就足够了.您还需要每个元素的排名(联合查找所需的排名).

Disjoint need to associate a rank and a parent (in the forest tree) to each element. Since you might want to work with any kind of data you may,for example, not always want to use a map for the parent: with integer an array is sufficient. You also need a rank foe each element (the rank needed for the union-find).

你需要两个属性":

• one 将一个整数关联到每个元素(第一个模板参数)，排名
• 一个将元素与另一个元素相关联(第二个模板参数)，父亲

举个例子:

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

数组用于&rank[0], &parent[0]，模板中的类型为int*

Arrays are used &rank[0], &parent[0] to the type in the template is int*

对于更复杂的示例(使用地图)，您可以查看 Ugo 的答案.

For a more complex example (using maps) you can look at Ugo's answer.

您只是为算法提供了两种结构来存储他需要的数据(等级/父级).

You are just giving to the algorithm two structures to store the data (rank/parent) he needs.

这篇关于理解 boost::disjoint_sets的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！