首页 文章

从Boost Graph中删除多个顶点[重复]

提问于
浏览
2

这个问题在这里已有答案:

为什么在图表中没有同时删除多个顶点的例行程序?只有remove_vertex()如果顶点是 vecS 则非常昂贵 .

在boost / graph / detail / adjacency_list.hpp remove_vertex_dispatch() 起始行#1966例程中,它擦除给定节点,然后重新索引边缘 . 可以添加另一个例程,比如说要删除顶点的索引并且一次性擦除它们(如何?可以讨论)并且重新索引只发生一次?

我理解使用listS会使它成为常量,但并非所有算法都适用于listS,所以这是不可能的 .

1 回答

  • 3

    如果删除顶点,则无法重新索引所有边并更新矢量 . 这具有非局部成本,其至少与顶点的数量成线性,并且这可能确实是昂贵的 .

    话虽这么说,你可以使用的一种技术是在最初设置为true的每个顶点中缓存一个布尔值 . 现在,要删除顶点,请删除连接到顶点的所有边,并将顶点布尔值设置为false . 这样,删除时间只是局部的,你没有顶点数的线性时间 . 然后,您需要调整某些操作,例如迭代顶点,只选择那些布尔值设置为true的操作 .

    这种技术很常见,例如用于简化3D三角测量(您可以迭代地移除顶点,并希望本地成本快速) . 与listS相比,您仍然可以直接访问顶点(删除顶点后顶点句柄仍然有效) .

相关问题