Graph traversal: Difference between revisions
Jump to navigation
Jump to search
(→Output) |
|||
| Line 15: | Line 15: | ||
== Remarks == | == Remarks == | ||
# Without loss of generality, the graph is [[Basic graph definitions#Directed and undirected graphs|simple]]. | |||
# 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 processed nodes and/or arcs | # It may be reasonable to implement a graph traversal algorithm in the form of an iterator, which returns the processed nodes and/or the traversed arcs step-by-step. | ||
# [[Dijkstra|Dijkstra's algorithm]] may be implemented as a graph traversal that returns the nodes in ascending order of | # [[Dijkstra|Dijkstra's algorithm]] may be implemented as a graph traversal that returns the nodes in the order of finishing. In other words, in ascending order of the node distances (which is not unique, in general). | ||
# The common graph traversal algorithms deliver specific additional output besides the above-mentioned output sequence. | # The common graph traversal algorithms deliver specific additional output besides the above-mentioned output sequence. In each case, additional output is specified on the page of the respective algorithm. | ||
# '''Early termination:''' Often, graph traversal is used to find a path from some start node <math>s</math> to some other node <math>t</math>. In this case, the traversal may terminate earlier, when <math>t</math> is seen (if <math>t</math> is ''not'' reachable from <math>s</math>, the search must be exhaustive in order to prove that no path exists). | # '''Early termination:''' Often, graph traversal is used to find a path from some start node <math>s</math> to some other node <math>t</math>. In this case, the traversal may terminate earlier, namely when <math>t</math> is seen (if <math>t</math> is ''not'' reachable from <math>s</math>, the search must be exhaustive in order to prove that no path exists). | ||
Revision as of 10:45, 31 October 2014
Input
- A directed graph [math]\displaystyle{ G=(V,A) }[/math].
- A start node [math]\displaystyle{ s\in V }[/math].
Output
An ordered sequence, whose content is a permutation 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
- Without loss of generality, the graph is simple.
- 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 processed nodes and/or the traversed arcs step-by-step.
- Dijkstra's algorithm may be implemented as a graph traversal that returns the nodes in the order of finishing. In other words, in ascending order of the node distances (which is not unique, in general).
- The common graph traversal algorithms deliver specific additional output besides the above-mentioned output sequence. In each case, additional output is specified on the page of the respective algorithm.
- Early termination: Often, graph traversal is used to find a path from some start node [math]\displaystyle{ s }[/math] to some other node [math]\displaystyle{ t }[/math]. In this case, the traversal may terminate earlier, namely when [math]\displaystyle{ t }[/math] is seen (if [math]\displaystyle{ t }[/math] is not reachable from [math]\displaystyle{ s }[/math], the search must be exhaustive in order to prove that no path exists).