Back
Close

Definition

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Pseudo-code:

1  Depth-first search(Graph,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in Graph.adjacentEdges(v) do
9                  S.push(w)

Source: Wikipedia (license)

External resources

Depth First Search