Graph traversal: Difference between revisions
Jump to navigation
Jump to search
| Line 16: | Line 16: | ||
== Remarks == | == Remarks == | ||
# For the purpose of graph traversal, an undirected graph may be viewed as a directed graph: Replace each edge <math>\{v,w\}</math> by two arcs, <math>(v,w)<math> and <math>(w,v)</math>. | # For the purpose of graph traversal, an undirected graph may be viewed as a directed graph: Replace each edge <math>\{v,w\}</math> by two arcs, <math>(v,w)</math> and <math>(w,v)</math>. | ||
# It may be reasonable to implement a graph traversal algorithm in the form of an iterator, which returns the nodes one-by-one. | # It may be reasonable to implement a graph traversal algorithm in the form of an iterator, which returns the nodes one-by-one. | ||
# [[Dijkstra|Dijkstra's algorithm]] may be implemented as a graph traversal that returns the nodes in ascending order of their distances. | # [[Dijkstra|Dijkstra's algorithm]] may be implemented as a graph traversal that returns the nodes in ascending order of their distances. | ||
Revision as of 09:32, 10 October 2014
Input
- A directed graph [math]\displaystyle{ G=(V,A) }[/math].
- 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
Remarks
- 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].
- It may be reasonable to implement a graph traversal algorithm in the form of an iterator, which returns the nodes one-by-one.
- Dijkstra's algorithm may be implemented as a graph traversal that returns the nodes in ascending order of their distances.