**Definition:**

Depth First Search is an algorithm that traverse the nodes in the graph or tree. It always expand the deepest node in the tree. It uses stack data structure (LIFO queue – last in first out).

In the worst case, time complecity of DFS is O (b^m) and space complecity is O (bm). (b: braching factor, m: maximum depth of any node)

In backtracking search, a different type of DFS, memory usage is less than BFS. Its space complecity is O (m).

Properties of DFS:

- Completed, if the graph or tree is finite. (Incomplete in infinite tree or graph),
- Uses stack (LIFO),
- O (b^m) is time complecity of DFS,
- O (bm) is space complecity of DFS.

**How Does It Work?**

1. The root node is expanded.

2. The successors nodes are expanded.

3. First node in the stack (last node entered the stack) is popped and expanded.

4. This goes on until the last node is expanded (visited).

In the figure below, you can see the order of nodes expanded.

Order of Nodes Expanded in DFS

**Animation:**

For better understanding, go to this animation page.

**Pseudocode:**

A recursive implementation of DFS: [1]

procedureDFS(G,v): labelvas discoveredfor alledges fromvtowinG.adjacentEdges(v)doifvertexwis not labeled as discoveredthenrecursively call DFS(G,w)

A non-recursive implementation of DFS: [2]

procedureDFS-iterative(G,v): letSbe a stackS.push(v)whileSis not emptyv←S.pop()ifvis not labeled as discovered: labelvas discoveredfor alledges fromvtowinG.adjacentEdges(v)doS.push(w)

**References:**

[1] Goodrich and Tamassia; Cormen, Leiserson, Rivest, and Stein

[2] Kleinberg and Tardos

Artificial Intelligence A Modern Approach, S.Russell, P. Norvig, Third Edition,

Figures from: http://en.wikipedia.org