Editing Depth-first search (section)

==Pseudocode==
{{Tree traversal demo|method=pre-order|noselectmethod=1|caption=Interactive depth-first search demonstration}}
A recursive implementation of DFS:<ref>Goodrich and Tamassia; Cormen, Leiserson, Rivest, and Stein</ref>
 '''procedure''' DFS(''G'', ''v'') '''is'''
     label ''v'' as discovered
     '''for all''' directed edges from ''v'' to ''w that are'' '''in''' ''G''.adjacentEdges(''v'') '''do'''
         '''if''' vertex ''w'' is not labeled as discovered '''then'''
             recursively call DFS(''G'', ''w'')

A non-recursive implementation of DFS with worst-case space complexity <math>O(|E|)</math>, with the possibility of duplicate vertices on the stack:<ref>Page 93, Algorithm Design, Kleinberg and Tardos</ref>
 '''procedure''' DFS_iterative(''G'', ''v'') '''is'''
     let ''S'' be a stack
     ''S''.push(''v'')
     '''while''' ''S'' is not empty '''do'''
         ''v'' = ''S''.pop()
         '''if''' ''v'' is not labeled as discovered '''then'''
             label ''v'' as discovered
             '''for all''' edges from ''v'' to ''w'' '''in''' ''G''.adjacentEdges(''v'') '''do''' 
                 ''S''.push(''w'')
[[File:Graph.traversal.example.svg|alt=An undirected graph with edges AB, BD, BF, FE, AC, CG, AE|right|200x200px|The example graph, copied from above]]
These two variations of DFS visit the neighbors of each vertex in the opposite order from each other: the first neighbor of ''v'' visited by the recursive variation is  the first one in the list of adjacent edges, while in the iterative variation the first visited neighbor is the last one in the list of adjacent edges. The recursive implementation will visit the nodes from the example graph in the following order: A, B, D, F, E, C, G. The non-recursive implementation will visit the nodes as: A, E, F, B, D, C, G.

The non-recursive implementation is similar to [[breadth-first search]] but differs from it in two ways: 
# it uses a stack instead of a queue, and
# it delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before adding the vertex.
If {{mvar|G}} is a [[Tree (data structure)|tree]], replacing the queue of the breadth-first search algorithm with a stack will yield a depth-first search algorithm. For general graphs, replacing the stack of the iterative depth-first search implementation with a queue would also produce a breadth-first search algorithm, although a somewhat nonstandard one.<ref>{{Cite web|title=Stack-based graph traversal ≠ depth first search|url=https://11011110.github.io/blog/2013/12/17/stack-based-graph-traversal.html|access-date=2020-06-10|website=11011110.github.io}}</ref>

Another possible implementation of iterative depth-first search uses a stack of [[Iterator|iterators]] of the list of neighbors of a node, instead of a stack of nodes. This yields the same traversal as recursive DFS.<ref>{{Cite book|last=Sedgewick, Robert|url=http://worldcat.org/oclc/837386973|title=Algorithms in Java.|date=2010|publisher=Addison-Wesley|isbn=978-0-201-36121-6|oclc=837386973}}</ref>
 '''procedure''' DFS_iterative(''G'', ''v'') '''is'''
     let ''S'' be a stack
     label ''v'' as discovered
     ''S''.push(iterator of ''G''.adjacentEdges(''v''))
     '''while''' ''S'' is not empty '''do'''
         '''if''' ''S''.peek().hasNext() '''then'''
             ''w'' = ''S''.peek().next()
             '''if''' ''w'' is not labeled as discovered '''then'''
                 label ''w'' as discovered
                 ''S''.push(iterator of ''G''.adjacentEdges(''w''))
         '''else'''
             ''S''.pop()