Searching: BFS vs DFS comparison

Why searching is necessary in AI

For most AI problems (puzzles, route finding, planning, game playing) there is no direct algorithm that gives the solution. The problem is modelled as a state space and the solution is found by searching for a sequence of actions from the initial state to the goal. Search is also needed to find the best solution among many and to explore alternatives systematically.

Blind (uninformed) search

A blind search uses only the problem definition (initial state, operators, goal test). It has no additional knowledge about how close a state is to the goal, and expands nodes in a fixed order. Examples: BFS, DFS, uniform-cost, depth-limited and iterative deepening search.

Example tree used for both searches

            A
          /   \
         B     C
        / \   / \
       D   E F   G(goal)

Breadth First Search (BFS)

Expands the shallowest unexpanded node first, using a FIFO queue.

1. Put start node in queue.
2. Remove first node n; if goal -> stop.
3. Add all children of n to the END of the queue.
4. Repeat from step 2.

Order of visiting: A, B, C, D, E, F, G. Queue: [A] → [B,C] → [C,D,E] → [D,E,F,G] ... goal G found at depth 2.

Depth First Search (DFS)

Expands the deepest unexpanded node first, using a LIFO stack (or recursion).

1. Put start node on stack.
2. Pop node n; if goal -> stop.
3. Push children of n on the TOP of the stack.
4. Repeat from step 2.

Order of visiting: A, B, D, E, C, F, G. It goes down a branch until it reaches a leaf or dead end, then backtracks.

Comparison of performance criteria

Let b = branching factor, d = depth of shallowest goal, m = maximum depth of the tree.

Remarks: BFS is complete and optimal but needs exponential memory (the main drawback). DFS needs far less memory but may get stuck in infinite paths and may find a longer solution. For example with b = 10 and d = 6, BFS may store about 10^6 nodes while DFS stores about 60.