Imagine being trapped in a maze and trying to find the exit.
Some people explore all nearby paths first, while others go deep into one path before turning back.
Computers solve such problems using search algorithms.
In Artificial Intelligence, Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental algorithms used to explore paths in a maze.
In this blog, we will learn how BFS and DFS solve a maze step by step, understand their working using queues and stacks, and compare how each algorithm behaves while searching for the goal.
Maze Description
The maze is represented as a set of connected nodes.
Each node represents a position in the maze, and edges represent valid paths between positions.
The objective is to find a path from the Initial State (Start) to the Goal State (Exit) without crossing walls.
Let’s treat this as a graph search problem with nodes
S, A, B, C, D, E, F, G, H, I, J, K, L, M, N, Key.
Goal node = Key
Problem: Maze Traversal using BFS and DFS
Given
- A maze with a Start node (S) and a Goal node (Key)
- Allowed moves: Up, Down, Left, Right
- Some paths are blocked (e.g., J is blocked)
Objective
- Traverse the maze using:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Record:
- Order of visiting nodes
- Final path from S → Key
BFS
Let us first solve the maze using Breadth-First Search (BFS).
🟦 PART A: Breadth-First Search (BFS)
🔹 Key Idea
BFS explores the maze level by level using a queue.
It always finds the shortest path in an unweighted maze.
🔹 BFS Rules Used
- Data structure: Queue (FIFO)
- Nodes are expanded level by level
- When a node is visited first time, record its parent
- Stop when Key is reached
✅ BFS Step-by-Step Table
| Step | Visited Node | Queue after Expansion |
| 0 | – | {S} |
| 1 | S | {A, D} |
| 2 | A | {D, B, E} |
| 3 | D | {B, E, H} |
| 4 | B | {E, H, C, F} |
| 5 | E | {H, C, F, I} |
| 6 | H | {C, F, I, K} |
| 7 | C | {F, I, K, G} |
| 8 | F | {I, K, G} |
| 9 | I | {K, G, L} |
| 10 | K | {G, L} |
| 11 | G | {L, Key} |
| 12 | Key | {L} → STOP |
Order of Node Traversal (BFS)
Order of node traversal =
Order in which nodes are VISITED / DEQUEUED in BFS
So we simply list the Visited Node column in order.
BFS Traversal Order
S → A → D → B → E → H → C → F → I → K → G → Key
This shows how BFS explored the maze level by level
BFS Parent Table
| Node | Parent |
| A | S |
| D | S |
| B | A |
| E | A |
| H | D |
| C | B |
| F | B |
| I | E |
| K | H |
| G | C |
| L | I |
| Key | G |
Final Path from Initial State to Goal State
👉 Important
Final path is NOT traversal order
It is obtained by BACKTRACKING using parent information.
🔁 Backtracking from Goal (Key)
Key ← G ← C ← B ← A ← S
Reverse it to get start → goal:
✅ FINAL BFS PATH
S → A → B → C → G → Key
Now let us solve the same maze using Depth-First Search (DFS).
PART B: Depth-First Search (DFS)
🔹 Key Idea
DFS explores deeply along one path before trying another.
It does NOT guarantee the shortest path.
🔹 DFS Rules Used
- Strategy: Go deep first
- Movement order (example): Right → Down → Left → Up
- Backtrack when a dead-end is reached
- Stop when Key is found
- Pop node from stack
- Mark it visited
- Push all unvisited children (right child first, so left is popped first)
🟦 DFS TABLE
| Step | Visited Node | Stack after Expansion |
| 0 | – | {S} |
| 1 | S | {D, A} |
| 2 | A | {D, E, B} |
| 3 | B | {D, E, F, C} |
| 4 | C | {D, E, F, G} |
| 5 | G | {D, E, F, Key} |
| 6 | Key | {D, E, F} → STOP |
Order of Node Traversal (DFS)
👉 Order of traversal =
Order in which nodes are POPPED from the stack
S → A → B → C → G → Key
Final Path from Initial State to Goal State
🔁 Parent relationships (DFS)
A ← S
B ← A
C ← B
G ← C
Key ← G
🔁 Backtracking from Goal
Key ← G ← C ← B ← A ← S
Reverse it:
✅ FINAL DFS PATH
S → A → B → C → G → Key