BFS and DFS are the two fundamental ways to explore a graph. Every single graph algorithm builds on one of these. Master them, and graph problems become way less scary.
In simple language, imagine we’re exploring a maze. BFS checks all rooms one step away, then all rooms two steps away, spreading outward like ripples. DFS picks one path and goes as deep as possible before backtracking.
Visual Comparison
BFS — Level by Level (Queue)
Level 0
1
↓
Level 1
2
3
↓
Level 2
4
5
6
Visit order: 1 → 2 → 3 → 4 → 5 → 6. Finds shortest path in unweighted graphs.
DFS — Go Deep First (Stack/Recursion)
1
↓
2
↓
4
↓
5
backtrack
↗
_
3
↓
6
Visit order: 1 → 2 → 4 → 5 → 3 → 6. Great for exploring all paths, backtracking.
BFS Implementation
BFS uses a queue — first in, first out. We process nodes level by level. This is why BFS naturally gives us the shortest path in unweighted graphs.
// BFS traversal on adjacency list
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
while (queue.length > 0) {
const node = queue.shift(); // dequeue front
console.log(node); // process node
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // enqueue
}
}
}
}# BFS traversal on adjacency list
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft() # dequeue front
print(node) # process node
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) # enqueue// BFS traversal on adjacency list
void bfs(List<List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll(); // dequeue front
System.out.println(node); // process node
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}Key detail: We mark nodes as visited when we add them to the queue, not when we process them. This prevents duplicates in the queue.
DFS Implementation
DFS goes deep before going wide. We can implement it with recursion (implicit stack) or an explicit stack.
Recursive DFS
// DFS recursive on adjacency list
function dfs(graph, node, visited = new Set()) {
visited.add(node);
console.log(node); // process node
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}# DFS recursive on adjacency list
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node) # process node
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)// DFS recursive on adjacency list
void dfs(List<List<Integer>> graph, int node, Set<Integer> visited) {
visited.add(node);
System.out.println(node); // process node
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}Iterative DFS
Same logic, but we manage the stack ourselves. Useful when recursion depth might cause a stack overflow.
// DFS iterative on adjacency list
function dfsIterative(graph, start) {
const visited = new Set();
const stack = [start];
while (stack.length > 0) {
const node = stack.pop(); // pop from top
if (visited.has(node)) continue;
visited.add(node);
console.log(node); // process node
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) stack.push(neighbor);
}
}
}# DFS iterative on adjacency list
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop() # pop from top
if node in visited:
continue
visited.add(node)
print(node) # process node
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)// DFS iterative on adjacency list
void dfsIterative(List<List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited.contains(node)) continue;
visited.add(node);
System.out.println(node);
for (int neighbor : graph.get(node))
if (!visited.contains(neighbor)) stack.push(neighbor);
}
}Grid Traversal: Number of Islands
Grids are just graphs in disguise. Each cell is a node. Its neighbors are the 4 (or 8) adjacent cells. The classic problem: count connected groups of 1s in a 2D grid.
// Number of Islands — DFS on grid
function numIslands(grid) {
let count = 0;
const rows = grid.length, cols = grid[0].length;
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
if (grid[r][c] !== '1') return;
grid[r][c] = '0'; // mark visited by sinking
dfs(r + 1, c); dfs(r - 1, c); // down, up
dfs(r, c + 1); dfs(r, c - 1); // right, left
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === '1') { dfs(r, c); count++; }
return count;
}# Number of Islands — DFS on grid
def num_islands(grid):
count = 0
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited by sinking
dfs(r + 1, c); dfs(r - 1, c) # down, up
dfs(r, c + 1); dfs(r, c - 1) # right, left
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count// Number of Islands — DFS on grid
int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') { dfs(grid, r, c); count++; }
return count;
}
void dfs(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
if (grid[r][c] != '1') return;
grid[r][c] = '0'; // mark visited
dfs(grid, r + 1, c); dfs(grid, r - 1, c);
dfs(grid, r, c + 1); dfs(grid, r, c - 1);
}The trick: Instead of maintaining a separate visited set, we modify the grid in place — change '1' to '0' when we visit a cell. This is the standard approach for grid DFS problems.
Connected Components
Sometimes we need to count how many separate groups (connected components) exist. The pattern is simple: loop through all nodes, BFS/DFS from each unvisited one, and count.
// Count connected components in undirected graph
function countComponents(n, edges) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Set();
let count = 0;
for (let i = 0; i < n; i++) {
if (!visited.has(i)) {
bfs(graph, i, visited); // or dfs
count++;
}
}
return count;
}# Count connected components in undirected graph
def count_components(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
for i in range(n):
if i not in visited:
bfs(graph, i, visited) # or dfs
count += 1
return count// Count connected components in undirected graph
int countComponents(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) { graph.get(e[0]).add(e[1]); graph.get(e[1]).add(e[0]); }
Set<Integer> visited = new HashSet<>();
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited.contains(i)) { bfs(graph, i, visited); count++; }
}
return count;
}BFS vs DFS: When to Use Which?
| Situation | Use | Why |
|---|---|---|
| Shortest path (unweighted) | BFS | BFS explores level by level, guarantees minimum steps |
| Explore all paths / backtracking | DFS | Natural fit for recursion and trying all options |
| Cycle detection | DFS | Track the recursion stack to detect back edges |
| Topological sort | DFS (or BFS with Kahn’s) | Post-order DFS gives reverse topological order |
| Level-order anything | BFS | We process one level at a time |
| Connected components | Either | Both work equally well |
Complexity
Both BFS and DFS visit every node and every edge exactly once:
- Time: O(V + E) for adjacency list
- Space: O(V) for the visited set + queue/stack
These two patterns are the backbone of graph algorithms. Everything from shortest paths to topological sort to cycle detection builds directly on BFS and DFS.