I'm trying to write my own version of connected components discovery using the breadth-first search algorithm included in the Boost Graph Library and I need to access the ancestor (the vertex which leads to the discovery of the current vertex) vertex from 开发者_Python百科withing the discover_vertex callback of my visitor to set the component number of the current vertex. Any way it can be done easily ?
Create an examine_vertex callback that records the vertex being examined (popped from the queue). This vertex will be the ancestor of whatever vertex is being discovered.
From the pseudo code in BGL's BFS documentation:
vis.examine_vertex(u, g) is invoked in each vertex as it is removed from the queue.
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)
精彩评论