Depth-first search

Definition

Depth-first search Algorithmic problem: Graph Traversal Prerequisites: Type of algorithm: loop Auxiliary data: A stack whose elements are nodes in . Each node has a current arc , which is either or an outgoing arc of . Each node has a Boolean label with semantics "is marked". Abstract view

Invariant: After iterations: The nodes marked so far are the lexicographically first nodes from . The arcs traversed in forward direction are the arcs of the tree that is the union of the lexicographically first paths from to all marked nodes. Stack contains the nodes on the lexicographically first path of the node marked last, in the order from to that node. For each node , is the lexicographically first outgoing arc of that has not yet been considered for going forward from (or , if no such arc exists). Variant: increases by . Break condition: .

Induction basis

Abstract view:

has one element: root .

Root is marked, all other nodes are unmarked. Implementation: Obvious. Proof: Nothing to show.

Induction step

Abstract view: If the current node has at least one outgoing arc to an unmarked node, traverse the lexicographically first of them to its target node and mark that node. Otherwise, go back along the path in until the current node does have such an outgoing arc, and traverse the first such arc in the list. Implementation: Let denote the top element of . While : Pop the top element from . If , terminate the algorithm. Let denote the new top element of . While and the target node of is marked, let the new be the next arc after in the list of outgoing arcs of (or , if no such arc exists). Push the target node of onto and mark it. Correctness: Since terminates the main loop, the first step and the first execution of Step 2.1 are well defined: at that moment, there indeed is a top element ready to be read and removed from . Due to Step 2.2, all further executions of Step 2.1 and all executions of Steps 2.3 and 2.4 are well defined, too. Obviously, the loop in Step 2 goes backwards along the path encoded in until there is an opportunity to go forward. Due to the prefix property, always contains the lexicographically first path to the current top element during the backtracking. Since is not marked, is the first arc from some lexicographically preceding node to . Therefore, when is pushed onto , the current contents of comprises the lexicographically first path to .

Complexity

Statement: The asymptotic complexity is in in the worst case, where and . If all nodes of are reachable from , it is also in the best and worst case. Proof: Note that every node is pushed at most once onto because a marked (=already pushed) node is skipped in Step 2.4. Therefore, the number of forward steps is in in the worst case. Clearly, the number of removals from is in in the worst case as well. Also note that each arc is considered at most once for going forward because an outgoing arc of becomes the current arc at most once. No other operation is executed more often than the stack operations and these arc operations. In summary, this gives in the worst case. Each node of that is reachable from will be seen by the search. Therefore, if all nodes are reachable, the number of push (and pop) operations is in in any case. Since a node is only removed from after all of its outgoing arcs were seen, all arcs will eventually be seen in that case, so the total number of arc inspections is then in .

Further information

Depth-first search could alternatively be implemented as a more fine-grained loop in which, in each iteration, exactly one forward or backward step over an arc is performed.

Pseudocode

DFS(G)

for each vertex u ∈ V [G]

do color[u] ← WHITE

π[u] ← NIL

time ← 0

do if color[u] == WHITE

then DFS-VISiT(u)

DFS-VISIT(u)

color[u] ← GRAY

time ← time + 1

d[u] ← time

for each v ∈ Adj[u]

do if color[v] = WHITE

then π [v] ← u

DFS-VISIT(v)

color[u] ← BLACK

f[u] ← time ← time + 1