Cómo acceder al vértice ancestro durante una búsqueda en amplitud con el Boost Graph Library?

Question

Estoy tratando de escribir mi propia versión del descubrimiento componentes conectados usando el algoritmo de búsqueda en anchura incluida en la Boost Graph Library y necesito para acceder al antecesor (el vértice que conduce al descubrimiento del vértice actual) vértice de devolución de llamada en el canto discover_vertex de mi visitante para establecer el número de componentes del vértice actual. Cualquier forma en que se puede hacer fácilmente?

Answer 1

Crea una devolución de llamada examine_vertex que registra el vértice siendo examinada (reventado de la cola). Este vértice será el ancestro de cualquier vértice que se está descubriendo.

Desde el pseudo código en BFS documentación del BGL :

  

vis.examine_vertex (u, g) se invoca   en cada vértice, ya que se elimina de   la cola.

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)