Depth- first search (DFS)

Starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

Order in which the nodes are visited

DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn't finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.

Worst case performance: O( | V | + | E | ) for explicit graphs traversed without repetition, O(bd) for implicit graphs with branching factor b searched to depth d.

Worst case space complexity: O( | V | ) if entire graph is traversed without repetition, O(longest path length searched) for implicit graphs without elimination of duplicate nodes.

Pseudocode

Input: A graph G and a vertex v of G

Output: A labeling of the edges in the connected component of v as discovery edges and back edges

1  procedure DFS(G,v):
2      label v as explored
3      for all edges e in G.incidentEdges(v) do
4          if edge e is unexplored then
5              w ← G.opposite(v,e)
6              if vertex w is unexplored then
7                  label e as a discovery edge
8                  recursively call DFS(G,w)
9          else
10             label e as a back edge