Definition
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 >
Creation
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. |
Preconditions:
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. |
Operations
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. |
void | algorithm.init(OutAdjIt s) | |
initializes the internal stack with s. | ||
Stacktype& | algorithm.get_stack() | gives direct access to internal stack. |
Implementation
Each operation requires constant time. Therefore, a normal depth-first search needs (m + n) time.