开发者

How to access the ancestor vertex during a breadth-first search with the Boost Graph Library?

开发者 https://www.devze.com 2023-01-20 01:48 出处:网络
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 l

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)
0

精彩评论

暂无评论...
验证码 换一张
取 消