Repeated depth-first search: Difference between revisions
(Created page with "== General information == '''Algorithmic problem:''' Exhaustive graph traversal '''Type of algorithm:''' loop '''Additional output:''' cf. DFS '''Specific characte...") |
No edit summary |
||
| Line 18: | Line 18: | ||
== Correctness == | == Correctness == | ||
Obviously, all nodes are finished eventually. For two nodes <math>v,w\in V</math> that are finished in the same DFS, the specific characteristic follows from the fact that DFS fulfills it. So assume <math>v</math> is seen in an earlier DFS than <math>w</math>. Since <math>v</math> is also earlier finished than <math>w</math>, the specific characteristic is fulfilled for <math>v</math> and <math>w</math> unless there is a path from <math>v</math> to <math>w</math>. However, if such a path existed, <math>w</math> had been seen in the same DFS as <math>v</math>. | Obviously, all nodes are finished eventually. For two nodes <math>v,w\in V</math> that are finished in the same DFS, the specific characteristic follows from the fact that DFS fulfills it. So assume <math>v</math> is seen in an earlier DFS than <math>w</math>. Since <math>v</math> is also earlier finished than <math>w</math>, the specific characteristic is fulfilled for <math>v</math> and <math>w</math> unless there is a path from <math>v</math> to <math>w</math>. However, if such a path existed, <math>w</math> had been seen in the same DFS as <math>v</math> | ||
== Complexity == | |||
'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math>. | |||
'''Proof:''' Follows immediately from the linear asymptotic complexity of [[DFS]] and the fact that each node and each arc is touched in only one [[DFS]]. | |||
Revision as of 17:54, 8 October 2014
General information
Algorithmic problem: Exhaustive graph traversal
Type of algorithm: loop
Additional output: cf. DFS
Specific characteristic: cf. DFS
Abstract View
While there are nodes not yet seen:
- Select a start node [math]\displaystyle{ s }[/math] from the unseen nodes.
- Apply aDFS starting at [math]\displaystyle{ S. }[/math]
Correctness
Obviously, all nodes are finished eventually. For two nodes [math]\displaystyle{ v,w\in V }[/math] that are finished in the same DFS, the specific characteristic follows from the fact that DFS fulfills it. So assume [math]\displaystyle{ v }[/math] is seen in an earlier DFS than [math]\displaystyle{ w }[/math]. Since [math]\displaystyle{ v }[/math] is also earlier finished than [math]\displaystyle{ w }[/math], the specific characteristic is fulfilled for [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] unless there is a path from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math]. However, if such a path existed, [math]\displaystyle{ w }[/math] had been seen in the same DFS as [math]\displaystyle{ v }[/math]
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(|V|+|A|) }[/math].
Proof: Follows immediately from the linear asymptotic complexity of DFS and the fact that each node and each arc is touched in only one DFS.