C++ 从图中删除顶点

3he 以下使用 boost.1.46.1 进行编译

#include <boost/graph/adjacency_list.hpp>

struct Node {
  int id;
};

struct Edge {
  int source;
  int target;
  int weight;
};

int main() {
  /* an adjacency_list like we need it */
  typedef boost::adjacency_list<
    boost::setS, // edge container
    boost::listS, // vertex container
    boost::bidirectionalS, // directed graph
    Node, Edge> Graph;

  typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

  Graph gp1;

  std::cout << "Number of vertices 1: " << boost::num_vertices(gp1) << std::endl;
  Vertex v1 = boost::add_vertex(gp1);
  Vertex v2 = boost::add_vertex(gp1);

  std::cout << "Number of vertices 2: " << boost::num_vertices(gp1) << std::endl;

  gp1[v1].id = 3;
  gp1[v2].id = 4;

  Graph gp2(gp1);

  std::cout << "Number of vertices 3: " << boost::num_vertices(gp2) << std::endl;

  boost::remove_vertex(v2, gp2);

  std::cout << "Number of vertices 4: " << boost::num_vertices(gp1) << std::endl;
  std::cout << "Number of vertices 5: " << boost::num_vertices(gp2) << std::endl;

  boost::graph_traits<Graph>::vertex_iterator it, end;
  for (boost::tie( it, end ) = vertices(gp2); it != end; ++it) {
    if ( gp2[*it].id == 3 ) {
      boost::remove_vertex(*it, gp2);
    }
  }

  std::cout << "Number of vertices 6: " << boost::num_vertices(gp1) << std::endl;
  std::cout << "Number of vertices 7: " << boost::num_vertices(gp2) << std::endl;

  return 0;
}

在删除 v2 时，gp2 如何知道 v2：“boost::remove_vertex(v2, gp2)” 为什么gp1的顶点数减少了1？

为什么它在“boost::remove_vertex(*it, gp2)”处给出分段错误 我该如何解决它？

请注意，sehe 的解决方案仅适用于 VertexList=listS 的图，特别不适用于 VertexList=vecS 的图。另请注意，通常您不能存储顶点描述符或迭代器并稍后删除它们，因为这个来自 Boost Graph Library 网站 http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/adjacency_list.html:

void remove_vertex(vertex_descriptor u, adjacency_list& g)

...如果 adjacency_list的VertexList模板参数为vecS，则所有 图的顶点描述符、边描述符和迭代器是 因该操作而无效。内置的 vertex_index_t 属性 每个顶点都被重新编号，以便在操作之后顶点 索引仍然形成一个连续的范围 [0, num_vertices(g))。 ...