|
|
#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> dfs(G& g,V* v,GApredicate(V)* f = 0);
List_of_p<V> dfs_u(G& g,V* v,GApredicate(V)* f = 0);
Given a Graph g, these functions start at Vertex v and perform a depth-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 those without the suffix treat the Graph 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 and e is the number of Edges in the component.
For breadth-first traversal, use bfs(3C++).