高效地扩展图形边缘集合

Question

我从图形中有一组边缘，并且想要用与任何边缘共享一个顶点的所有边缘来扩展它。我怎样才能有效地与boost::graph s？

我能够想出的唯一方法是提取所有源和目标顶点的天真解决方案，使用boost::adjacent_vertices获取所有邻接点，然后使用boost::edge创建所有新边缘。有没有更好的方法来做到这一点？

上下文：图顶点是地形三角剖分的质心，边连接相应三角形相邻的顶点（如此类的双图）。我期望扩展的边集合对应于被阻止的三角形间路径，并且阻塞区域正在扩大。这个区域是圆形的，所以我会用上面的天真方法看到的大部分边缘都将成为该组的一部分。

Answer 1

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

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