Graph traversal

Basic definitions

1. Basic graph definitions

Input

1. A directed graph [math]\displaystyle{ G=(V,A) }[/math].
2. A start node [math]\displaystyle{ s\in V }[/math].

Output

An ordered sequence, whose content is a permutation of all nodes of [math]\displaystyle{ G }[/math] that can be reached from [math]\displaystyle{ s }[/math] via paths in [math]\displaystyle{ G }[/math].

Known algorithms

1. Depth-first search
2. Breadth-first search

Remarks

1. Without loss of generality, the graph is simple.
2. For the purpose of graph traversal, an undirected graph may be viewed as a directed graph: Replace each edge [math]\displaystyle{ \{v,w\} }[/math] by two arcs, [math]\displaystyle{ (v,w) }[/math] and [math]\displaystyle{ (w,v) }[/math].
3. It may be reasonable to implement a graph traversal algorithm in the form of an iterator, which returns the processed nodes and/or the traversed arcs step-by-step. In such an implementation, the loop is turned inside-out, so the client code has full control over the loop: may terminate the loop early, suspend the loop and resume its execution later on, insert additional functionality in every iteration, etc.
4. Dijkstra's algorithm may be implemented as a graph traversal that returns the nodes in the order of finishing. In other words, in ascending order of the node distances (which is not unique, in general).
5. The common graph traversal algorithms deliver specific additional output besides the above-mentioned output sequence. In each case, additional output is specified on the page of the respective algorithm.
6. Early termination: Often, graph traversal is used to find a path from some start node [math]\displaystyle{ s }[/math] to some other node [math]\displaystyle{ t }[/math]. In this case, the traversal may terminate earlier, namely when [math]\displaystyle{ t }[/math] is seen (if [math]\displaystyle{ t }[/math] is not reachable from [math]\displaystyle{ s }[/math], the search must be exhaustive in order to prove that no path exists).