c++ - 如何在使用 Boost Graph Library 进行广度优先搜索期间访问祖先顶点？

Question

我正在尝试使用 Boost Graph Library 中包含的广度优先搜索算法编写我自己的连接组件发现版本，并且我需要从 withing 访问祖先（导致发现当前顶点的顶点）顶点访问者的 discover_vertex 回调来设置当前顶点的组件号。有什么方法可以轻松完成吗？

Answer 1

创建一个 Exam_vertex 回调来记录正在检查的顶点（从队列中弹出）。该顶点将是正在发现的任何顶点的祖先。

从 BGL 的BFS 文档中的伪代码：

vis.examine_vertex(u, g) 在从队列中移除的每个顶点中被调用。

BFS(G, s)
  for each vertex u in V[G]
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
  end for
  color[s] := GRAY 
  d[s] := 0 
  ENQUEUE(Q, s)
  while (Q != Ø) 
    u := DEQUEUE(Q)                   # `u` is recorded in examine_vertex callback 
    for each vertex v in Adj[u]
      if (color[v] = WHITE)
        color[v] := GRAY
        d[v] := d[u] + 1  
        p[v] := u  
        ENQUEUE(Q, v)                 # `v` is discovered, `u` is its ancestor.
      else
        if (color[v] = GRAY) 
          ...
        else 
          ...
    end for
    color[u] := BLACK
  end while
  return (d, p)