DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 

dfs(3C++)


dfs, dfs_u -- depth-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> dfs(G& g,V* v,GApredicate(V)* f = 0);
       List_of_p<V> dfs_u(G& g,V* v,GApredicate(V)* f = 0);

Description

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.

Complexity

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

Notes

For breadth-first traversal, use bfs(3C++).

References

Graph_alg(3C++), List(3C++) bfs(3C++), comps(3C++),
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004