Graph traversal

From Algowiki
Revision as of 09:31, 10 October 2014 by Weihe (talk | contribs) (→‎Output)
Jump to navigation Jump to search

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 seach]


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)\lt math\gt and \lt math\gt (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.