Repeated depth-first search: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 5: Line 5:
'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


'''Additional output:''' cf. [[Depth-first search|DFS]].
'''Additional output:''' the same as for [[Depth-first search|DFS]] with one modification: Instead of an arborescence, the algorithm returns a [[Basic graph definitions#Forests, trees, branchings, arborescences|branching]] that is a [[Basic graph definitions#Subgraphs|spanning subgraph]] of <math>G</math> (cf. [[Depth-first search|DFS]]).


'''Specific characteristic:'''
'''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]]).
analogous to the parenthetical output order of [[Depth-first search|DFS]]: 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>.


== Abstract View ==
== Abstract View ==
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 [[Depth-first search|DFS]] starting at <math>s</math>, second type of output order.
# Apply a [[Depth-first search|DFS]] starting at <math>s</math>, parenthetical output order.


== 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 ==
== Complexity ==
Line 24: Line 24:
'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math>.
'''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]].
'''Proof:''' Follows immediately from the linear asymptotic complexity of [[Depth-first search|DFS]] and the fact that each node and each arc is touched in only one [[DFS]].

Latest revision as of 07:28, 3 November 2014

General information

Algorithmic problem: Exhaustive graph traversal

Type of algorithm: loop

Additional output: the same as for DFS with one modification: Instead of an arborescence, the algorithm returns a branching that is a spanning subgraph of [math]\displaystyle{ G }[/math] (cf. DFS).

Specific characteristic: analogous to the parenthetical output order of DFS: 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].

Abstract View

While there are nodes not yet seen:

  1. Select a start node [math]\displaystyle{ s }[/math] from the unseen nodes.
  2. Apply a DFS starting at [math]\displaystyle{ s }[/math], parenthetical 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.