Depth-first search: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(62 intermediate revisions by 4 users not shown)
Line 3: Line 3:
[[Category:Tree Algorithms]]
[[Category:Tree Algorithms]]
[[Category:Graph Traversal]]
[[Category:Graph Traversal]]
[[Category:Check:Checkup]]


== General information ==
== General information ==
Line 10: Line 11:
'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


== Abstract view ==
== Definitions ==
 
'''Definitions:'''
# For each node, an arbitrary but fixed ordering of the outgoing arcs is assumed. An arc <math>(v,w)</math> preceding an arc <math>(v,w')</math> in this ordering is called '''lexicographically smaller''' than <math>(v,w)</math>.
# For each node, an arbitrary but fixed ordering of the outgoing arcs is assumed. An arc <math>(v,w)</math> preceding an arc <math>(v,w')</math> in this ordering is called '''lexicographically smaller''' than <math>(v,w)</math>.
# Let <math>p</math> and <math>p'</math> be two paths that start from the same node <math>v\in V</math>, but may or may not have the same endnode. Let <math>w</math> be the last common node such that the subpaths of <math>p</math> and <math>p'</math> from <math>v</math> up to <math>w</math> are identical (possibly <math>v=w</math>). If the next arc of <math>p</math> is lexicographically smaller than the next arc of <math>p'</math>, <math>p</math> is said to be '''lexicograpically smaller''' than <math>p'</math>.
# Let <math>p</math> and <math>p'</math> be two paths that start from the same node <math>v\in V</math>, but may or may not have the same end node. Let <math>w</math> be the last common node such that the subpaths of <math>p</math> and <math>p'</math> from <math>v</math> up to <math>w</math> are identical (possibly <math>v=w</math>). If the next arc of <math>p</math> from <math>w</math> onwards is lexicographically smaller than the next arc of <math>p'</math> from <math>w</math> onwards, <math>p</math> is said to be '''lexicograpically smaller''' than <math>p'</math>. Note that the lexicographically ''smallest'' path from <math>v\in V</math> to <math>w\in V</math> is well defined and unique.
# Note that the lexicographically smallest path from <math>v\in V</math> to <math>w\in V</math> is well defined and unique. With respect to a starting node <math>s\in V</math>, a node <math>v\in V</math> is '''lexicographically smaller''' than <math>w\in V</math> if the lexicographically smallest path from <math>s</math> to <math>v</math> is lexicographically smaller than the lexicographically smallest path from <math>s</math> to <math>w</math>.
# With respect to a starting node <math>s\in V</math>, a node <math>v\in V</math> is '''lexicographically smaller''' than <math>w\in V</math> if the lexicographically smallest path from <math>s</math> to <math>v</math> is lexicographically smaller than the lexicographically smallest path from <math>s</math> to <math>w</math>.
# In all of the above cases, the reverse relation is called '''lexicographically larger'''.
# In all of the above cases, the reverse relation is called '''lexicographically larger'''.
# A node <math>v\in V</math> is '''lexicographically smaller''' (resp., '''lexicograpically larger''') than a path <math>p</math> if the lexicographically smallest path from the start node of <math>p</math> to <math>v</math> is lexicographically smaller (resp., larger) than <math>p</math>. (Note the asymmetry: In both cases, the lexicographically ''smallest'' path to <math>v</math> is used.)
# A node <math>v\in V</math> is '''lexicographically smaller''' (resp., '''lexicograpically larger''') than a path <math>p</math> if <math>v</math> does not belong to <math>p</math> and the lexicographically smallest path from the start node of <math>p</math> to <math>v</math> is lexicographically smaller (resp., larger) than <math>p</math>. (Note the asymmetry: In both cases, the lexicographically ''smallest'' path to <math>v</math> is used.)
# In all cases, we also say '''precedes''' and '''succeeds''', respectively, instead of "is lexicograpically smaller/larger".
 
== Abstract view ==


'''Additional output:'''
'''Additional output:'''
Each node has two Boolean labels with semantics, "is seen" and "is finished".
# Each node has two Boolean labels with semantics, "is seen" and "is finished".
# An [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] <math>A=(V',A')</math> rooted at <math>s</math> such that <math>V'\subseteq V</math> is the set of all nodes reachable from <math>s</math> (including <math>s</math>). For each node <math>v\in V'</math>, the path from <math>s</math> to <math>v</math> in <math>A</math> is the lexicographically smallest <math>(s,v)</math>-path in <math>G</math>.


'''Specific characteristic:'''
'''Specific characteristic:'''
The nodes may be returned either in lexicographic order or (alternatively or simultaneously) in '''parenthetical order''', that is:
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>.
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>.
'''Remark:'''
''Parenthetical'' refers to the following intuition: Whenever a node is seen, open a parenthesis, and close it once the node is finished. The result is a correct parenthetial expression: Two parentheses are either disjoint, or one is nested in the other one.


'''Auxiliary data:'''
'''Auxiliary data:'''
# A stack <math>S</math> whose elements are nodes in <math>V</math>.
# A [[Sets and sequences#Stacks and queues|stack]] <math>S</math> whose elements are nodes in <math>V</math>.
# Each node  has a '''current arc''' <math>a_v\in V</math>, which is either void or an outgoing arc <math>a_v=(v,w)</math> of <math>v</math>.
# Each node  has a '''current arc''' <math>a_v\in V</math>, which is either void or an outgoing arc <math>a_v=(v,w)</math> of <math>v</math>. (May be viewed as an iterator over the list of all outgoing arcs.)


'''Invariant:'''  
'''Invariant:'''  
Before and after each iteration:
Before and after each iteration:
# <math>S</math> forms a path <math>p</math> from the start node to some other node, that is, the order of the nodes on <math>p</math> is the order in which they appear in <math>S</math> (start node <math>s</math> at the bottom of <math>S</math>).
# <math>S</math> forms a path <math>p</math> from the start node <math>s</math> to some other node, that is, the order of the nodes on <math>p</math> is the order in which they appear in <math>S</math> (start node <math>s</math> at the bottom of <math>S</math>).
# For each node not yet seen, the current arc is the first arc (or void if the node has no outgoing arcs).
# For each node not yet seen, the current arc is the first arc (or void if the node has no outgoing arcs).
# For each node <math>v</math> on <math>p</math>:
# For each node <math>v</math> on <math>p</math>:
## If there are arcs <math>(v,w)\in A</math> such that <math>w</math> is not seen, the current arc equals or precedes the first such arc.
## If there are arcs <math>(v,w)\in A</math> such that <math>w</math> is not yet seen, the current arc equals or precedes the first such arc.
## The subpath of <math>p</math> from the start node to <math>v</math> is the lexicographically first path from the start node to <math>v</math>.
## The subpath of <math>p</math> from the start node <math>s</math> to <math>v</math> is the lexicographically first <math>(s,v)</math>-path.
# The nodes on <math>p</math> are seen but not finished. Let <math>p'</math> denote the concatenation of <math>p</math> with the current arc <math>a</math> of the last node of <math>p</math>. The nodes that are lexicographically smaller than <math>p'</math> are seen and finished, and the nodes that lexicographically succeed <math>p'</math> are neither seen nor finished. (Note that nothing is said about the head of <math>a</math>).
# The nodes on <math>p</math> are seen but not finished. Let <math>p+a</math> denote the concatenation of <math>p</math> with the current arc <math>a</math> of the last node of <math>p</math>. The nodes that are lexicographically smaller than <math>p+a</math> are seen and finished, and the nodes that lexicographically succeed <math>p+a</math> are neither seen nor finished. (Note that nothing is said about the head of <math>a</math>).


'''Variant:''' Either one node is finished or the current arc of one node is moved forward.
'''Variant:''' Either one node is seen for the first time or finished, or (inclusive) the current arc of one node is moved forward.


'''Break condition:''' <math>S=\emptyset</math>.
'''Break condition:''' <math>S=\emptyset</math>.
Line 44: Line 51:
== Induction basis ==
== Induction basis ==


'''Abstract view:''' No node is finished. The start node is seen, no other node is seen. The start node is the only element of <math>S</math>. The current arc of the start node is its first outgoing arc. The out sequence is empty.
'''Abstract view:''' No node is finished. The start node <math>s</math> is seen, no other node is seen. The start node is the only element of <math>S</math>. The current arc of each node is its first outgoing arc. If the nodes are to be returned in lexicographic order, the start node <math></math> is, initially, the only member of the output sequence; otherwise, the initial output sequence is empty. Arborescence <math>A</math> is initialized so as to contain <math>s</math> and nothing else.


'''Implementation:''' Obvious.
'''Implementation:''' Obvious.
Line 54: Line 61:
'''Abstract view:'''
'''Abstract view:'''
# Let <math>v</math> be the last node of <math>p</math> (=the top element of <math>S</math>).
# Let <math>v</math> be the last node of <math>p</math> (=the top element of <math>S</math>).
# While the current arc of <math>v</math> is not void and the head of the current arc is labeled as seen, move the current arc one step forward.
# While the current arc of <math>v</math> is not void and while the head of the current arc is labeled as seen: Move the current arc one step forward.
# If the current arc of <math>v</math> is not void, add the current arc to <math>T</math>, push the head of the current arc on <math>S</math> and label this node as seen.
# If the current arc of <math>v</math> is not void, say, <math>a_v=(v,w)</math>:
# Otherwise, remove <math>v</math> from <math>S</math> and label <math>v</math> as finished.
## Insert <math>w</math> and <math>(v,w)</math> in <math>A</math>.
## Push <math>w</math> on <math>S</math>.
## Label <math>w</math> as seen.
## If the output order is the lexicographical one: Append <math>w</math> to the output sequence.
# Otherwise:
## Remove <math>v</math> from <math>S</math>
## Label <math>v</math> as finished.
## If the output order is the parenthetical one: Put <math>v</math> in the output sequence.


'''Implementation:''' Obvious.
'''Implementation:''' Obvious.


'''Proof:'''
'''Proof:'''
The loop variant is obviously fulfilled.
The loop ''variant'' is obviously fulfilled.


The first point of the invariant is obviously fulfilled. The second point follows from the fact that the current arc of a node is initialized to be the node's very firstoutgoing arc and only changed after the node is labeled as seen. Point 3.1 follows from the fact that the current arc never skips an arc to an unseen node.
The first point of the ''invariant'' is obviously fulfilled, too. The second point follows from the fact that the current arc of a node is initialized to be the node's very first outgoing arc and only changed after the node is labeled as ''seen''. Point 3.1 follows from the fact that, in step 2, the current arc never skips an arc that points to an unseen node.


For a contradiction to 3.2, note that any lexicographically smaller path <math>p'</math> has at least one node that is lexicographically smaller than <math>p</math>. By induction hypothesis (point 4), these nodes are finished. Let <math>w</math> denote the last finished node on <math>p'</math>. Since <math>v</math> is not finished immediately before the iteration, <math>w</math> has a successor on <math>p'</math>, which is unfinished. However, obviously, a nodes is marked finished not before all of its immediate successors are finished.
For point 3.2, let <math>p'</math> be the lexicographically smallest <math>(s,v)</math>-path. Moreover, let <math>w\neq v</math> be the last node on <math>p</math> and <math>p'</math> such that both paths are identical from <math>s</math> to <math>w</math> (possibly, <math>w=s</math>). Further, let <math>u</math> and <math>u'</math> be the immediate successors of <math>w</math> on <math>p</math> and <math>p'</math>, respectively. Then <math>u'</math> has been seen before <math>u</math> because <math>(w,u)</math> is the arc over which <math>u</math> was seen for the first time, and <math>(w,u')</math> precedes <math>(w,u)</math>. Note that <math>v</math> has not been seen earlier than <math>u</math> (in fact, later than <math>u</math>, unless <math>v=u</math>). In summary, <math>u'</math> has been seen before <math>v</math>. Since there is a path from <math>u'</math> to <math>v</math>, the correctness proof [[#Correctness|below]] will prove that <math>v</math> was finished before <math>u'</math>. This contradicts the induction hypothesis (point 4 of the invariant).


When a node is pushed on <math>S</math>, it is neither seen nor finished immediately before that iteration and labaled as seen in that iteration. This proves the first sentence. The other statements of point 4 follow from the observation that <math>p</math> increases lexicographically in each iteration.
When a node is pushed on <math>S</math>, it is neither seen nor finished immediately before that iteration and then labeled as seen in that iteration. The node is finished when it leaves <math>S</math>. Both facts together give the first sentence of point 4. The other statements of point 4 follow from the observation that the concatenation of <math>p</math> with the current arc of the endnode of <math>p</math> increases lexicographically in each iteration in which Step 3 applies.


== Correctness ==
== Correctness ==


It is easy to see that each operation of the algorithm is well defined. Due to the variant, the loop terminates after a finite number of steps. Immediately before the last iteration, <math>p</math> consists of the start node <math>s</math> only, and the current arc of <math>s</math> is void. Therefore, ''all'' nodes reachable from <math>s</math> except for <math>s</math> itself are lexicographically smaller than <math>p</math>. Due to point 4 of the invariant, all of these nodes are finished. In the last iteration, <math>s</math> is finished as well.
It is easy to see that each operation of the algorithm is well defined. Due to the variant, the loop terminates after a finite number of steps. Immediately before the last iteration, <math>p</math> consists of the start node <math>s</math> only, and the current arc of <math>s</math> is void. Therefore, ''all'' nodes reachable from <math>s</math> except for <math>s</math> itself are lexicographically smaller than <math>p</math> at that moment. Due to point 4 of the invariant, all of these nodes are finished. In the last iteration, <math>s</math> is finished as well.
 
So, it remains to show that the specific characteristic is fulfilled in both cases.
Due to point 3.2 of the invariant, a node is seen for the first time via its lexicographically smallest path from <math>s</math>. Since the current path increases lexicographically in each iteration, the nodes are labeled as seen in lexicographic order. In summary, the lexicographical order is correct.


Suppose for a contradictin that the specific characteristic is not fulfilled by <math>v,w\in V</math>. That is, <math>v</math> is seen and finished before <math>w</math>. Consider the situation immediately after the iteration in which <math>v</math> is finished. So, in this moment, <math>w</math> is not yet finished. By assumption, there is a path from <math>v</math> to <math>w</math> in <math>G</math>. There are two successive nodes on this path, <math>x</math> and <math>y</math>, such that <math>x</math> is finished and <math>y</math> is not at that moment. However, obviously, <math>x</math> cannot be finished prior to <math>y</math>.
So consider the second, the parenthetical case.
Let <math>v</math> be seen before <math>w</math> and assume there is a path from <math>v</math> to <math>w</math>. We have to show that <math>w</math> is finished prior to <math>v</math>. Let <math>p'</math> denote the lexicographically smallest <math>(v,w)</math>-path. There is a stage in which this path is a subpath of the current path <math>p</math>. Clearly, <math>v</math> cannot be removed from <math>S</math> before <math>w</math>. This proves the claim.


== Complexity ==
== Complexity ==


'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math> in the best and worst case.
'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math> in the worst case.
 
'''Proof:'''
For every node reachable from <math>s</math> (including <math>s</math>), the algorithm processes each of its outgoing arcs exactly once. And from each of these nodes, the algorithm goes backwards exactly once. Obviously, each of these steps requires a constant number of operations.
 
== Remark ==


'''Proof:''' From every node, the algorithm goes forward at most once for each of its outgoing arcs. And from each node, th algorithm goes backwards only once. Obviously, each of these steps requires a constant number of operations.
Alternatively, DFS could be implemented as a recursive procedure. However, this excludes the option to implement DFS as an iterator, which means to turn the loop inside-out (cf. remarks on [[Graph traversal|graph traversal]]).


== Pseudocode ==  
== Pseudocode recursive implementation ==  




Line 104: Line 127:
:''color''[''u''] &larr; BLACK
:''color''[''u''] &larr; BLACK
:''f''[''u''] &larr; ''time'' &larr; ''time'' + 1
:''f''[''u''] &larr; ''time'' &larr; ''time'' + 1
== Pseudocode stack implementation ==
====DFS(''s'')====
: ''S = new Stack()''
: ''s.IsSeen = true''
: ''S.push(s)''
: '''while''' ''S'' &ne; &empty;
:: ''n'' = ''S.peek()''
:: ''a'' = ''(v, w)'' = ''n.nextArc()''
:: '''if''' ''a'' == ''null''
::: ''n.IsFinised'' = ''true''
::: ''S.pop()''
:: '''else if''' ''w.IsSeen'' == ''false''
::: ''w.IsSeen'' = ''true''
::: ''S.push(w)''

Latest revision as of 06:52, 26 October 2015


General information

Algorithmic problem: Graph traversal

Type of algorithm: loop

Definitions

  1. For each node, an arbitrary but fixed ordering of the outgoing arcs is assumed. An arc [math]\displaystyle{ (v,w) }[/math] preceding an arc [math]\displaystyle{ (v,w') }[/math] in this ordering is called lexicographically smaller than [math]\displaystyle{ (v,w) }[/math].
  2. Let [math]\displaystyle{ p }[/math] and [math]\displaystyle{ p' }[/math] be two paths that start from the same node [math]\displaystyle{ v\in V }[/math], but may or may not have the same end node. Let [math]\displaystyle{ w }[/math] be the last common node such that the subpaths of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ p' }[/math] from [math]\displaystyle{ v }[/math] up to [math]\displaystyle{ w }[/math] are identical (possibly [math]\displaystyle{ v=w }[/math]). If the next arc of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ w }[/math] onwards is lexicographically smaller than the next arc of [math]\displaystyle{ p' }[/math] from [math]\displaystyle{ w }[/math] onwards, [math]\displaystyle{ p }[/math] is said to be lexicograpically smaller than [math]\displaystyle{ p' }[/math]. Note that the lexicographically smallest path from [math]\displaystyle{ v\in V }[/math] to [math]\displaystyle{ w\in V }[/math] is well defined and unique.
  3. With respect to a starting node [math]\displaystyle{ s\in V }[/math], a node [math]\displaystyle{ v\in V }[/math] is lexicographically smaller than [math]\displaystyle{ w\in V }[/math] if the lexicographically smallest path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] is lexicographically smaller than the lexicographically smallest path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ w }[/math].
  4. In all of the above cases, the reverse relation is called lexicographically larger.
  5. A node [math]\displaystyle{ v\in V }[/math] is lexicographically smaller (resp., lexicograpically larger) than a path [math]\displaystyle{ p }[/math] if [math]\displaystyle{ v }[/math] does not belong to [math]\displaystyle{ p }[/math] and the lexicographically smallest path from the start node of [math]\displaystyle{ p }[/math] to [math]\displaystyle{ v }[/math] is lexicographically smaller (resp., larger) than [math]\displaystyle{ p }[/math]. (Note the asymmetry: In both cases, the lexicographically smallest path to [math]\displaystyle{ v }[/math] is used.)
  6. In all cases, we also say precedes and succeeds, respectively, instead of "is lexicograpically smaller/larger".

Abstract view

Additional output:

  1. Each node has two Boolean labels with semantics, "is seen" and "is finished".
  2. An arborescence [math]\displaystyle{ A=(V',A') }[/math] rooted at [math]\displaystyle{ s }[/math] such that [math]\displaystyle{ V'\subseteq V }[/math] is the set of all nodes reachable from [math]\displaystyle{ s }[/math] (including [math]\displaystyle{ s }[/math]). For each node [math]\displaystyle{ v\in V' }[/math], the path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] in [math]\displaystyle{ A }[/math] is the lexicographically smallest [math]\displaystyle{ (s,v) }[/math]-path in [math]\displaystyle{ G }[/math].

Specific characteristic: The nodes may be returned either in lexicographic order or (alternatively or simultaneously) in parenthetical order, that is: 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].

Remark: Parenthetical refers to the following intuition: Whenever a node is seen, open a parenthesis, and close it once the node is finished. The result is a correct parenthetial expression: Two parentheses are either disjoint, or one is nested in the other one.

Auxiliary data:

  1. A stack [math]\displaystyle{ S }[/math] whose elements are nodes in [math]\displaystyle{ V }[/math].
  2. Each node has a current arc [math]\displaystyle{ a_v\in V }[/math], which is either void or an outgoing arc [math]\displaystyle{ a_v=(v,w) }[/math] of [math]\displaystyle{ v }[/math]. (May be viewed as an iterator over the list of all outgoing arcs.)

Invariant: Before and after each iteration:

  1. [math]\displaystyle{ S }[/math] forms a path [math]\displaystyle{ p }[/math] from the start node [math]\displaystyle{ s }[/math] to some other node, that is, the order of the nodes on [math]\displaystyle{ p }[/math] is the order in which they appear in [math]\displaystyle{ S }[/math] (start node [math]\displaystyle{ s }[/math] at the bottom of [math]\displaystyle{ S }[/math]).
  2. For each node not yet seen, the current arc is the first arc (or void if the node has no outgoing arcs).
  3. For each node [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math]:
    1. If there are arcs [math]\displaystyle{ (v,w)\in A }[/math] such that [math]\displaystyle{ w }[/math] is not yet seen, the current arc equals or precedes the first such arc.
    2. The subpath of [math]\displaystyle{ p }[/math] from the start node [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] is the lexicographically first [math]\displaystyle{ (s,v) }[/math]-path.
  4. The nodes on [math]\displaystyle{ p }[/math] are seen but not finished. Let [math]\displaystyle{ p+a }[/math] denote the concatenation of [math]\displaystyle{ p }[/math] with the current arc [math]\displaystyle{ a }[/math] of the last node of [math]\displaystyle{ p }[/math]. The nodes that are lexicographically smaller than [math]\displaystyle{ p+a }[/math] are seen and finished, and the nodes that lexicographically succeed [math]\displaystyle{ p+a }[/math] are neither seen nor finished. (Note that nothing is said about the head of [math]\displaystyle{ a }[/math]).

Variant: Either one node is seen for the first time or finished, or (inclusive) the current arc of one node is moved forward.

Break condition: [math]\displaystyle{ S=\emptyset }[/math].

Induction basis

Abstract view: No node is finished. The start node [math]\displaystyle{ s }[/math] is seen, no other node is seen. The start node is the only element of [math]\displaystyle{ S }[/math]. The current arc of each node is its first outgoing arc. If the nodes are to be returned in lexicographic order, the start node [math]\displaystyle{ }[/math] is, initially, the only member of the output sequence; otherwise, the initial output sequence is empty. Arborescence [math]\displaystyle{ A }[/math] is initialized so as to contain [math]\displaystyle{ s }[/math] and nothing else.

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

  1. Let [math]\displaystyle{ v }[/math] be the last node of [math]\displaystyle{ p }[/math] (=the top element of [math]\displaystyle{ S }[/math]).
  2. While the current arc of [math]\displaystyle{ v }[/math] is not void and while the head of the current arc is labeled as seen: Move the current arc one step forward.
  3. If the current arc of [math]\displaystyle{ v }[/math] is not void, say, [math]\displaystyle{ a_v=(v,w) }[/math]:
    1. Insert [math]\displaystyle{ w }[/math] and [math]\displaystyle{ (v,w) }[/math] in [math]\displaystyle{ A }[/math].
    2. Push [math]\displaystyle{ w }[/math] on [math]\displaystyle{ S }[/math].
    3. Label [math]\displaystyle{ w }[/math] as seen.
    4. If the output order is the lexicographical one: Append [math]\displaystyle{ w }[/math] to the output sequence.
  4. Otherwise:
    1. Remove [math]\displaystyle{ v }[/math] from [math]\displaystyle{ S }[/math]
    2. Label [math]\displaystyle{ v }[/math] as finished.
    3. If the output order is the parenthetical one: Put [math]\displaystyle{ v }[/math] in the output sequence.

Implementation: Obvious.

Proof: The loop variant is obviously fulfilled.

The first point of the invariant is obviously fulfilled, too. The second point follows from the fact that the current arc of a node is initialized to be the node's very first outgoing arc and only changed after the node is labeled as seen. Point 3.1 follows from the fact that, in step 2, the current arc never skips an arc that points to an unseen node.

For point 3.2, let [math]\displaystyle{ p' }[/math] be the lexicographically smallest [math]\displaystyle{ (s,v) }[/math]-path. Moreover, let [math]\displaystyle{ w\neq v }[/math] be the last node on [math]\displaystyle{ p }[/math] and [math]\displaystyle{ p' }[/math] such that both paths are identical from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ w }[/math] (possibly, [math]\displaystyle{ w=s }[/math]). Further, let [math]\displaystyle{ u }[/math] and [math]\displaystyle{ u' }[/math] be the immediate successors of [math]\displaystyle{ w }[/math] on [math]\displaystyle{ p }[/math] and [math]\displaystyle{ p' }[/math], respectively. Then [math]\displaystyle{ u' }[/math] has been seen before [math]\displaystyle{ u }[/math] because [math]\displaystyle{ (w,u) }[/math] is the arc over which [math]\displaystyle{ u }[/math] was seen for the first time, and [math]\displaystyle{ (w,u') }[/math] precedes [math]\displaystyle{ (w,u) }[/math]. Note that [math]\displaystyle{ v }[/math] has not been seen earlier than [math]\displaystyle{ u }[/math] (in fact, later than [math]\displaystyle{ u }[/math], unless [math]\displaystyle{ v=u }[/math]). In summary, [math]\displaystyle{ u' }[/math] has been seen before [math]\displaystyle{ v }[/math]. Since there is a path from [math]\displaystyle{ u' }[/math] to [math]\displaystyle{ v }[/math], the correctness proof below will prove that [math]\displaystyle{ v }[/math] was finished before [math]\displaystyle{ u' }[/math]. This contradicts the induction hypothesis (point 4 of the invariant).

When a node is pushed on [math]\displaystyle{ S }[/math], it is neither seen nor finished immediately before that iteration and then labeled as seen in that iteration. The node is finished when it leaves [math]\displaystyle{ S }[/math]. Both facts together give the first sentence of point 4. The other statements of point 4 follow from the observation that the concatenation of [math]\displaystyle{ p }[/math] with the current arc of the endnode of [math]\displaystyle{ p }[/math] increases lexicographically in each iteration in which Step 3 applies.

Correctness

It is easy to see that each operation of the algorithm is well defined. Due to the variant, the loop terminates after a finite number of steps. Immediately before the last iteration, [math]\displaystyle{ p }[/math] consists of the start node [math]\displaystyle{ s }[/math] only, and the current arc of [math]\displaystyle{ s }[/math] is void. Therefore, all nodes reachable from [math]\displaystyle{ s }[/math] except for [math]\displaystyle{ s }[/math] itself are lexicographically smaller than [math]\displaystyle{ p }[/math] at that moment. Due to point 4 of the invariant, all of these nodes are finished. In the last iteration, [math]\displaystyle{ s }[/math] is finished as well.

So, it remains to show that the specific characteristic is fulfilled in both cases. Due to point 3.2 of the invariant, a node is seen for the first time via its lexicographically smallest path from [math]\displaystyle{ s }[/math]. Since the current path increases lexicographically in each iteration, the nodes are labeled as seen in lexicographic order. In summary, the lexicographical order is correct.

So consider the second, the parenthetical case. Let [math]\displaystyle{ v }[/math] be seen before [math]\displaystyle{ w }[/math] and assume there is a path from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math]. We have to show that [math]\displaystyle{ w }[/math] is finished prior to [math]\displaystyle{ v }[/math]. Let [math]\displaystyle{ p' }[/math] denote the lexicographically smallest [math]\displaystyle{ (v,w) }[/math]-path. There is a stage in which this path is a subpath of the current path [math]\displaystyle{ p }[/math]. Clearly, [math]\displaystyle{ v }[/math] cannot be removed from [math]\displaystyle{ S }[/math] before [math]\displaystyle{ w }[/math]. This proves the claim.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(|V|+|A|) }[/math] in the worst case.

Proof: For every node reachable from [math]\displaystyle{ s }[/math] (including [math]\displaystyle{ s }[/math]), the algorithm processes each of its outgoing arcs exactly once. And from each of these nodes, the algorithm goes backwards exactly once. Obviously, each of these steps requires a constant number of operations.

Remark

Alternatively, DFS could be implemented as a recursive procedure. However, this excludes the option to implement DFS as an iterator, which means to turn the loop inside-out (cf. remarks on graph traversal).

Pseudocode recursive implementation

DFS(G)

for each vertex uV [G]
do color[u] ← WHITE
π[u] ← NIL
time ← 0
do if color[u] == WHITE
then DFS-VISiT(u)


DFS-VISIT(u)

color[u] ← GRAY
timetime + 1
d[u] ← time
for each vAdj[u]
do if color[v] = WHITE
then π [v] ← u
DFS-VISIT(v)
color[u] ← BLACK
f[u] ← timetime + 1


Pseudocode stack implementation

DFS(s)

S = new Stack()
s.IsSeen = true
S.push(s)
while S ≠ ∅
n = S.peek()
a = (v, w) = n.nextArc()
if a == null
n.IsFinised = true
S.pop()
else if w.IsSeen == false
w.IsSeen = true
S.push(w)