理解 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.
相关文章