|
|
#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);
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.
O(max(v,e)), where v is the number of Vertices in the component and e is the number of Edges in the component.
For depth-first traversal, use dfs(3C++).