bfs(3C++)


bfs, bfs_u -- breadth-first traversal of Graphs

Synopsis

   #define GApredicate(T) ...  
   #define Graph_algdeclare(G,V,E) ...  
   #define Graph_algimplement(G,V,E) ...  
   Expanding Graph_algdeclare(G,V,E) produces the following text: 
       typedef int GApredicate(V)(const V* v); 
       List_of_p<V> bfs(G& g,V* v,GApredicate(V)* f = 0); 
       List_of_p<V> bfs_u(G& g,V* v,GApredicate(V)* f = 0); 

Description

Given a Graph g, these functions start at Vertex v and perform a breadth-first traversal of the connected component containing v (see comps(3C++)). They return a list of pointers to the Vertices in visitation order. As usual, functions with the _u suffix treat the Graph as undirected, while functions without the suffix treat it as directed. An optional client-supplied function will be called upon arrival at each Vertex; a zero returned by the function terminates the traversal.

Complexity

O(max(v,e)), where v is the number of Vertices in the component and e is the number of Edges in the component.

Notes

For depth-first traversal, use dfs(3C++).

References

Graph_alg(3C++), comps(3C++), dfs(3C++), List(3C++)
30 January 1998
© 1998 The Santa Cruz Operation, Inc. All rights reserved.