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.