Graph traversal

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. 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].
2. It may be reasonable to implement a graph traversal algorithm in the form of an iterator, which returns the processed nodes and/or arcs one-by-one.
3. Dijkstra's algorithm may be implemented as a graph traversal that returns the nodes in ascending order of their distances (which is not unique, in general).
4. The common graph traversal algorithms deliver specific additional output besides the above-mentioned output sequence.
5. 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, 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).