BFS stands for Breadth-First-Search
DFS stands for Depth-first search

A classic LeetCode problem “Number of Islands”:

Given a 2D grid map of 1s (land) and 0s (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
Input:
11000
11000
00100
00011
Output: 3

Although this problem is categorized under BFS, implementing it with DFS may be more intuitive.

Key differences between the two search algorithms

Assume we have an input grid:

1 1 0 0 0
1 1 1 1 0
1 0 1 0 0
1 0 0 0 0

• Both algorithms will return 1 as the answer

DFS Characteristics

1. DFS always prioritizes searching in one direction until reaching a dead end
2. Then explores other directions from the end node
3. Backtracks to previous nodes with unexplored paths
4. Operates like a stack (Last-In-First-Out)

• Search order assumption: ↑↓←→ (up, down, left, right)
• Traversal sequence:

1 6 0 0 0
2 5 7 9 0
3 0 8 0 0
4 0 0 0 0

• Starts at 1, reaches 4 via downward search. After backtracking, explores rightward to 5, then upward to 6. Continues to 7, 8, and finally 9.

BFS Characteristics

1. BFS explores all neighboring nodes first
2. Expands search layer by layer
3. Operates like a queue (First-In-First-Out)

• Search order assumption: ↑↓←→ (up, down, left, right)
• Traversal sequence:

1 3 0 0 0
2 5 7 9 0
4 0 8 0 0
6 0 0 0 0

• Starts with 1 in the queue [1]. Processes neighbors to get [2,3], then expands to [4,5], [6,7], and finally [8,9].

View source code on GitHub