2

我有一组来自图表的边,并希望使用与任何边共享顶点的所有边来扩展它。我怎样才能用boost::graphs 有效地做到这一点?

我能想出的唯一方法是提取所有源和目标顶点的幼稚解决方案,boost::adjacent_vertices用于获取所有邻接关系,然后使用boost::edge. 有没有更好的方法来做到这一点?

上下文:图顶点是地形三角剖分的质心,边连接对应三角形相邻的顶点(所以有点像对偶图)。我要扩展的边集对应于被阻塞的三角形间路径,并且被阻塞的区域正在扩展。该区域是圆形的,所以我使用上面的幼稚方法看到的大部分边缘已经是集合的一部分。

4

1 回答 1

1

不是在每个步骤中考虑所有相邻顶点来生成新边,而是使用属性映射来标记已经遇到的边。因此,您只需在每个步骤中考虑未标记的边缘。在将所有与它相关的边添加到您的集合后,会标记一个顶点。

鉴于 boost::graph 使用的内部数据结构要么是邻接列表,要么是邻接矩阵,我认为不可能有任何进一步的改进。

于 2011-09-08T14:12:14.750 回答