DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 

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++)
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004