How to Use a Breadth-First Search Algorithm

In partnership with

This week, we’re diving into one of the most useful graph traversal strategies you’ll ever use: Breadth-First Search (BFS). Whether you’re solving coding interview problems, navigating a maze, or building a recommendation system, BFS is a must-have in your toolbox.

What Is Breadth-First Search?

BFS is a graph traversal algorithm that explores nodes level by level. It starts at a source node and explores all its neighbors before moving on to the next layer of nodes. Think of it like ripples expanding in water. Each layer represents a new level of depth in the search.

It uses a queue to keep track of what to explore next. And that’s the key difference from Depth-First Search (DFS), which uses a stack.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(f"Visited: {node}")
            visited.add(node)
            queue.extend(graph[node] - visited)

Not comfortable with Python? It’s easy to get started. Here’s how to learn Python.

Short takeaway? This function takes a graph (represented as a dictionary of sets) and a starting node. It prints each visited node in the order BFS traverses it.

When Should You Use BFS?

• Finding the shortest path in an unweighted graph

• Crawling websites or analyzing social networks

• Solving puzzles like mazes or word ladders

• Building recommendation engines (e.g., people you may know)

• AI and game logic for exploring decision trees level-by-level

If you’ve ever used a GPS or a file search tool, you’ve seen BFS in action — behind the scenes.

Partner Message

Learn AI in 5 minutes a day

This is the easiest way for a busy person wanting to learn AI in as little time as possible:

1. Sign up for The Rundown AI newsletter

2. They send you 5-minute email updates on the latest AI news and how to use it

3. You learn how to become 2x more productive by leveraging AI

Sign up to start learning.

What Is Depth-First Search (DFS)?

Depth-First Search is a graph traversal algorithm that explores as far as possible along a branch before backtracking. Think of it like wandering down one hallway of a maze until you hit a wall, then turning around and trying the next path.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(f"Visited: {start}")
    for neighbor in graph[start] - visited:
        dfs(graph, neighbor, visited)

DFS uses a stack data structure either explicitly (with a stack) or implicitly through recursion. It’s the opposite of BFS, which explores level-by-level.

BFS vs. DFS

Where DFS dives deep into a graph before backtracking, BFS stays shallow, hitting every neighbor of the current node before moving to the next layer. This is what makes BFS ideal for finding the shortest path (by edge count) in unweighted graphs.

Related Reading