View source for Repeated depth-first search

== General information ==

'''Algorithmic problem:''' [[Exhaustive graph traversal]]

'''Type of algorithm:''' loop

'''Additional output:''' cf. [[Depth-first search|DFS]].

'''Specific characteristic:'''
Let <math>v,w\in V</math> such that <math>v</math> is seen before <math>w</math>. If there is a path from <math>v</math> to <math>w</math>, <math>w</math> is finished prior to <math>v</math> (cf. [[Depth-first search|DFS]]).

== Abstract View ==

While there are nodes not yet seen:
# Select a start node <math>s</math> from the unseen nodes.
# Apply a[[DFS]] starting at <math>S.</math>


== 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>


== 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]].