An instance algorithm of class GIT_DFS< OutAdjIt, Stacktype, Mark > is an implementation of an algorithm that traverses a graph in a depth first order. The stack used for the search must be provided by the caller and contains the source(s) of the search.
A next step may return a state which describes the last action. There are the following three possibilities:
Iterator version: There is an iterator version of this algorithm: DFS_It. Usage is similar to that of node iterators without the ability to go backward in the sequence.
#include < LEDA/graph/graph_iterator.h >
|GIT_DFS< OutAdjIt, Stacktype, Mark >||algorithm(const Stacktype& st, Mark& ma)|
|creates an instance algorithm of this class bound to the stack st and data accessor ma.|
|GIT_DFS< OutAdjIt, Stacktype, Mark >||algorithm(const Stacktype& st, Mark& ma, const OutAdjIt& ai)|
|creates an instance algorithm of this class bound to the stack st, data accessor ma and the adjacency iterator ai representing the source node of the depth first traversal.|
|void||algorithm.next_unseen()||Performs one iteration of the core loop of the algorithm for one unseen node of the graph.|
|dfs_return||algorithm.next()||Performs one iteration of the core loop of the algorithm.|
|OutAdjIt||algorithm.current()||returns the ``current'' iterator.|
|void||algorithm.finish_algo()||executes the algorithm until finished() is true, i.e. exactly if the stack is empty.|
|bool||algorithm.finished()||returns true if the internal stack is empty.|
|initializes the internal stack with s.|
|Stacktype&||algorithm.get_stack()||gives direct access to internal stack.|
Each operation requires constant time. Therefore, a normal depth-first search needs (m + n) time.