c++ - 在插入期间检测周期

Question

我有一个有向图。在运行时动态添加和删除新边。如果要添加到图中的边创建了一个循环，则不应添加该边。我将如何使用 BGL 执行此操作？

typedef boost::adjacency_list<
  boost::listS, boost::vecS,
  boost::directedS
  > Graph;

int main(int, char*[]){

  Graph G;
  add_edge(0, 1, G);
  add_edge(1, 2, G);
  add_edge(2, 3, G);
  add_edge(3, 0, G);  //creates cycle, should abort.

}

Answer 1

你会想在每次添加之前运行广度优先或深度优先搜索，看看是否会形成一个循环。它将形成当且仅当您正在添加边缘(u->v) 并且u 已经可以从v 到达。

这是我从 here 窃取的(希望有效的)代码

bool should_we_add(Graph &G) {
  typedef Graph::vertex_descriptor Vertex; 
  std::vector<int> distances(N, 0); // where N is number of vertices in your graph

  // The source vertex 
  Vertex s = boost::vertices(G)[u]; // this is your starting vertex 

  boost::breadth_first_search(G, s,
             boost::visitor(boost::make_bfs_visitor(boost::record_distances(&distances[0], boost::on_tree_edge())))); 

  if (distances[v] != 0) {
      // it is reachable, do NOT add the edge
      cout << "Cycle!" << endl;
      return false;
  }
  return true;
}