Repeated depth-first search: Difference between revisions
Line 14: | Line 14: | ||
While there are nodes not yet seen: | While there are nodes not yet seen: | ||
# Select a start node <math>s</math> from the unseen nodes. | # Select a start node <math>s</math> from the unseen nodes. | ||
# Apply a[[DFS]] starting at <math>s</math>, second type of output order. | # Apply a [[Depth-first search|DFS]] starting at <math>s</math>, second type of output order. | ||
== Correctness == | == Correctness == |
Revision as of 12:23, 10 October 2014
General information
Algorithmic problem: Exhaustive graph traversal
Type of algorithm: loop
Additional output: cf. DFS.
Specific characteristic: Let [math]\displaystyle{ v,w\in V }[/math] such that [math]\displaystyle{ v }[/math] is seen before [math]\displaystyle{ w }[/math]. If there is a path from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math], [math]\displaystyle{ w }[/math] is finished prior to [math]\displaystyle{ v }[/math] (cf. DFS).
Abstract View
While there are nodes not yet seen:
- Select a start node [math]\displaystyle{ s }[/math] from the unseen nodes.
- Apply a DFS starting at [math]\displaystyle{ s }[/math], second type of output order.
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.