Breadth-First Search Algorithm Explained with Examples

By Khaled Md Tuhidul Hossain · 2025-09-14 · Algorithms

BFS takes the opposite approach from DFS. Instead of diving deep, it explores all neighbors of a node before moving to the next level. Think of it like dropping a stone in water. The ripples expand outward evenly in all directions.

This level-by-level behavior gives BFS a superpower: it naturally finds the shortest path between two nodes in an unweighted graph. No extra work needed. That property alone makes it incredibly useful.

Interactive Visualization

Use the controls below to step through the algorithm or let it play automatically.

name: bfs
input: {"nodes": ["A", "B", "C", "D", "E", "F", "G"], "edges": [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["C", "G"]], "start": "A"}
speed: 700

How BFS Actually Works

You start at a node, visit all its direct neighbors, then visit all their unvisited neighbors, and so on. The trick is using a queue (first-in, first-out) instead of a stack. The queue ensures you process nodes in the order you discovered them.

Here's the graph we'll work through:

Starting from A, BFS visits nodes level by level:

• Level 0: A
• Level 1: B, C, D
• Level 2: E, F, G, H, I

So the traversal order is: A → B → C → D → E → F → G → H → I

See how it finishes all of level 1 before touching level 2? That's what makes shortest path calculations work.

Level-by-Level Traversal Visualized

Step-by-Step Queue Walkthrough

Now let's trace through the algorithm with the queue visible. This is where it really makes sense.

Notice how B, C, and D all get processed before any of their children. The queue enforces this ordering automatically.

Python Implementation

Here's a clean BFS implementation using Python's collections.deque, which gives you O(1) pops from the left side. Don't use a regular list for this, list.pop(0) is O(n) and it'll slow you down on large graphs.

Basic BFS Traversal

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


graph = {
    'A': ['B', 'C', 'D'],
    'B': ['E', 'F'],
    'C': ['G'],
    'D': ['H', 'I'],
    'E': [],
    'F': [],
    'G': [],
    'H': [],
    'I': []
}

print(bfs(graph, 'A'))
# Output: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']

One subtle thing: we add nodes to visited when we enqueue them, not when we dequeue them. This prevents the same node from being added to the queue multiple times. It's a common mistake that can cause bugs and slow things down.

BFS for Shortest Path

This is the version you'll actually use most often. It tracks the path back from destination to source using a parent dictionary.

from collections import deque

def bfs_shortest_path(graph, start, goal):
    if start == goal:
        return [start]

    visited = set([start])
    queue = deque([(start, [start])])

    while queue:
        node, path = queue.popleft()

        for neighbor in graph[node]:
            if neighbor == goal:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path exists


path = bfs_shortest_path(graph, 'A', 'H')
print(path)
# Output: ['A', 'D', 'H']

The path ['A', 'D', 'H'] has length 2, and you can verify there's no shorter way to get from A to H. BFS guarantees this.

BFS with Level Tracking

Sometimes you need to know which level each node belongs to. Here's how to track that.

from collections import deque

def bfs_levels(graph, start):
    visited = set([start])
    queue = deque([start])
    levels = {start: 0}

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                levels[neighbor] = levels[node] + 1
                queue.append(neighbor)

    return levels


print(bfs_levels(graph, 'A'))
# Output: {'A': 0, 'B': 1, 'C': 1, 'D': 1, 'E': 2, 'F': 2, 'G': 2, 'H': 2, 'I': 2}

When Should You Use BFS?

BFS shines whenever "closest" or "minimum steps" is part of the question.

Shortest Path in Unweighted Graphs

This is the classic use case. If every edge has the same weight (or no weight at all), BFS finds the shortest path. Period. You don't need Dijkstra for unweighted graphs, BFS is simpler and just as correct.

Think GPS navigation on a grid, minimum moves in a board game, or fewest hops between network routers.

Social Network Friend Suggestions

"People you may know" features often use BFS. Start from a user, find all friends (level 1), then friends-of-friends (level 2). Level 2 nodes who aren't already your friends become suggestions, and you can rank them by how many mutual connections you share.

from collections import deque

def friend_suggestions(social_graph, user):
    """Find friends-of-friends who aren't already direct friends."""
    direct_friends = set(social_graph[user])
    visited = set([user]) | direct_friends
    queue = deque(social_graph[user])
    suggestions = []

    for friend in queue:
        for fof in social_graph[friend]:
            if fof not in visited:
                visited.add(fof)
                suggestions.append(fof)

    return suggestions

Web Crawling

Web crawlers use BFS to discover pages. Start from a seed URL, fetch all links on that page (level 1), then fetch all links on those pages (level 2), and so on. BFS ensures you index pages closer to your seed first, which are usually more relevant.

You can also set a depth limit to avoid crawling the entire internet.

from collections import deque

def crawl(start_url, max_depth=3):
    visited = set([start_url])
    queue = deque([(start_url, 0)])

    while queue:
        url, depth = queue.popleft()
        if depth >= max_depth:
            continue

        # In real code, you'd fetch the page and parse links
        links = get_links(url)  # placeholder

        for link in links:
            if link not in visited:
                visited.add(link)
                queue.append((link, depth + 1))

    return visited

Time and Space Complexity

Same time complexity as DFS. The difference is in what they're good at, not how fast they run.

Space-wise, BFS can be hungrier than DFS in practice. For a balanced binary tree with a million leaf nodes, BFS would need to hold all those leaves in the queue at once. DFS would only need stack space proportional to the tree height (about 20 nodes). So think about the shape of your graph.

BFS vs DFS: When to Pick Which

Here's a practical guide:

• Need shortest path? BFS. Every time.
• Need to detect cycles? DFS is more natural for this.
• Exploring a tree? Either works, pick whichever fits your problem.
• Graph is very deep? BFS avoids stack overflow risks.
• Graph is very wide? DFS uses less memory.
• Topological sort? DFS is the standard approach.

Both algorithms are fundamental. You don't pick one over the other permanently. You pick the right one for the problem in front of you. Once you understand both, that choice becomes obvious.

BFS is clean, predictable, and gives you shortest paths for free. That's a pretty good deal for an algorithm that fits in about 15 lines of code.