1

Depth First Search Algorithm (DFS)

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.

300px-Depth-first-tree.svg

Order of Nodes Expanded in DFS

Animation:

For better understanding, go to this animation page.

Pseudocode:

A recursive implementation of DFS: [1]

procedure DFS(G,v):
   label v as discovered
   for all edges from v to w 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: [2]

procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
            vS.pop() 
            if v is not labeled as discovered:
                label v as discovered
                for all edges from v to w in G.adjacentEdges(v) do
                    S.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

7

Breadth-First Search Algorithm (BFS)

Definition:

Breadth-First Search Algorithm is a graph search algorithm. It begins from root node and continues to expand all neighbour node 1- level below.

In artificial intelligence, it is categorized as Uninformed (Blind) Search.

In worst case, the time complexity of this algorithm is O ( b ^d ). ( b: maximum branching factor of the search tree ;  d: depth of the least-cost solution )

In worst case, the space complexity of this algorithm is O ( b ^d ).

Properties of BFS:

  • Completed,
  • Finds the shallowest path,
  • Generates b + b^2 + b^3 + … + b^d = O( b^d ) nodes,
  • Space complexity (frontier size) is O (b ^ d ) .

How Does It Work?

  1. The root node is expanded.
  2. Then,  all successors of the root node are expanded,
  3. Then all their successors.

In detail: (from Wikipedia)

  1. Enqueue the root node,
  2. Dequeue a node
    • If the element sought is found in this node, quit the search and return a result.
    • Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
  3. If the queue is empty, every node on the graph has been examined – quit the search and return “not found”.
  4. If the queue is not empty, repeat from Step 2.

In the figure below, you can see the animated figure of BFS.

Animated_BFS

Animated Figure of BFS

In the figure below, you can see the order of nodes expanded (visited)

300px-Breadth-first-tree.svg

Order of Nodes Expandend in BFS

Animation:

For better understanding, go to this animation page.

Pseudocode:

1  procedure BFS(G,v) is
2      create a queue Q
3      create a vector set V
4      enqueue v onto Q
5      add v to V
6      while Q is not empty loop
7         t ← Q.dequeue()
8         if t is what we are looking for then
9            return t
10        end if
11        for all edges e in G.adjacentEdges(t) loop
12           u ← G.adjacentVertex(t,e)
13           if u is not in V then
14               add u to V
15               enqueue u onto Q
16           end if
17        end loop
18     end loop
19     return none
20 end BFS

 

References:

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

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