Graph traversal

Input

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

Output

A sequence 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 nodes 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.