了解的boost :: disjoint_sets [英] Understanding boost::disjoint_sets

问题描述

我需要使用boost :: disjoint_sets，但文档是我不清楚。是否有人可以解释每个模板参数意味着，或许举个小例子code创建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的离线至少共同祖先算法即 - 值类型应为顶点描述

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.

推荐答案

我可以从文档的理解：

不相交需要一个等级和家长（在森林树）的每个元素相关联。既然你可能希望与任何类型的数据的工作，你可能，例如，并不总是想用地图父：整数数组就足够了。您还需要一个敌人等级的每个元素（所需工会找到级）。

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).

您需要两个属性

• 一个给每个元素一个整数（第一个模板参数），排名
关联

• 一个到另一个元素（第二个模板参数），相关联的父亲

在一个例子：

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

阵列用于＆放大器;秩[0]，＆安培;父[0] 来在模板类型为为int *

有关更复杂的例子（利用地图），你可以看看乌戈的回答。

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！