DFS/BFS - Depth-First Search vs. Breadth-First Search

After completing this topic:

You will understand the difference between how DFS and BFS traverse a graph, and you will be able to determine which one to use based on the type of problem.

Two strategies for escaping a maze

You've entered a maze and come to a fork in the road. You have two strategies:

Strategy A: Choose one direction and go all the way to the end. If you hit a dead end, go back to the last fork and try a different path. This is like digging deep into one well.

Strategy B: At each fork, move one step forward in all directions. Then, at the next fork, move one step forward in all directions. This is like spreading out in concentric circles.

Strategy A is DFS (Depth-First Search), and Strategy B is BFS (Breadth-First Search).

DFS - Go all the way down one path

text

A
   / \
  B   C
 / \   \
D   E   F

Starting at A and traversing using DFS: A → B → D → (hit a dead end, backtrack) → E → (backtrack) → C → F

If you choose one path, you go all the way down it. When there's nowhere else to go, you backtrack and explore another path.

Implementation uses a Stack or Recursion:

python

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

The recursive call itself acts like a stack. The function calls itself, going deeper and deeper, and then returns, going back up.

BFS - Explore everything from the nearest

If you traverse the same tree using BFS: A → B → C → D → E → F

Starting at A, you first visit B and C, which are one step away. Then, you visit D, E, and F, which are two steps away. You explore in order of distance from the starting point.

Implementation uses a Queue:

python

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Because you process the nodes in the order they were added to the queue, the nearest nodes are visited first.

Key difference: Stack vs. Queue

The code for DFS and BFS is almost identical. The difference is only in which data structure is used to manage the next nodes to visit.

text

DFS: Stack (or Recursion) → Retrieves the last inserted element first → Depth-first
BFS: Queue              → Retrieves the first inserted element first → Breadth-first

Changing the data structure changes the order of traversal completely.

When to use which

DFS is suitable when:

You need to check if a path exists (yes/no)
You need to explore all possible cases (backtracking)
In a maze, you only need to find one exit
You want to use less memory (only store the current path)

BFS is suitable when:

You need to find the shortest path
You need to explore from the nearest first
Recommending "friends of friends" on a social network
Finding the closest server on a network

The most important distinction: Use BFS if you need the shortest distance, and DFS if you only need to check for existence.

Since BFS visits nodes starting from the nearest, the first path found is the shortest path. DFS explores in a depth-first manner, so it doesn't guarantee the shortest path.

Time Complexity

Both have a time complexity of O(V + E), where V is the number of nodes and E is the number of edges. All nodes are visited once, and all edges are checked once. The traversal order is different, but the total amount of work is the same.

The space complexity is different. DFS uses a stack proportional to the depth of the current exploration path. BFS uses a queue to store all nodes at the same level, so it uses more memory for wide graphs.

Key takeaway

DFS explores one direction to the end and backtracks when it hits a dead end. It uses a stack or recursion. BFS explores everything from the nearest. It uses a queue. BFS is suitable if you need the shortest path, and DFS is suitable if you only need to check for existence.

BioPlayground

DFS/BFS — Depth-First vs. Breadth-First