Come accedere al vertice antenato nel corso di una ricerca in ampiezza con il Boost Graph Library?

Question

Sto cercando di scrivere la mia versione di scoperta componenti collegati utilizzando l'algoritmo di ricerca in ampiezza compresa nel Boost Graph Library e ho bisogno di accedere l'antenato (il vertice che conduce alla scoperta del vertice corrente) vertex dal withing il callback discover_vertex del mio visitatore per impostare il numero dei componenti del vertice corrente. In qualsiasi modo lo si può fare facilmente?

Answer 1

Crea un callback examine_vertex che registra il vertice in esame (spuntato dalla coda). Questo vertice sarà l'antenato di qualsiasi vertice che viene scoperto.

Dalla pseudo codice in BFS documentazione del BGL :

  

vis.examine_vertex (u, g) viene richiamato   in ogni vertice come viene rimosso dalla   la coda.

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)