Graph traversal: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Input == # A directed graph <math>G=(V,A)</math>. # A '''start node''' <math>s\in V</math>. ''Output:''' A sequence of all nodes of <math>G</m...") |
No edit summary |
||
| Line 4: | Line 4: | ||
# A '''start node''' <math>s\in V</math>. | # A '''start node''' <math>s\in V</math>. | ||
== Output == | |||
A sequence of all nodes of <math>G</math> that can be reached | A sequence of all nodes of <math>G</math> that can be reached | ||
Revision as of 09:30, 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
Known algorithms
- Depth-first search
- [[Breadth-first seach]
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)\lt math\gt and \lt math\gt (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.