Breadth-First Search (BFS)

In the previous lesson, we learned what graphs are and how they represent real-world relationships such as roads, networks, and connections between people.

Now that we understand the structure of graphs, the next natural question is:

How do we explore a graph systematically?

Breadth-First Search, commonly called BFS, is one of the most fundamental algorithms used to traverse graphs.

What Is Breadth-First Search?

Breadth-First Search is a graph traversal algorithm that explores all neighboring nodes first before moving deeper.

In simple words, BFS moves:

Level by level.

It starts from a chosen source node, visits all nodes directly connected to it, then visits nodes at distance two, then distance three, and so on.

Real-World Intuition

Imagine you are looking for a person in a city.

First, you check all houses on your street. If the person is not found, you check the neighboring streets. Then the streets beyond that.

You do not go very deep into one road first — you expand outward evenly.

This is exactly how BFS works.

Why BFS Is Important

BFS is especially useful when:

• You want the shortest path in an unweighted graph
• You need to explore neighbors evenly
• You want to avoid going too deep too early

Many real systems such as routing protocols and recommendation engines use BFS-like logic internally.

The Core Idea Behind BFS

The key data structure behind BFS is a queue.

A queue follows the rule:

First In, First Out (FIFO)

This ensures that nodes are processed in the exact order they are discovered.

BFS Algorithm (Conceptual Steps)

At a high level, BFS follows these steps:

• Start from a source node
• Add it to a queue
• Mark it as visited
• Repeatedly visit neighbors in queue order

The visited check prevents infinite loops in cyclic graphs.

BFS Implementation (Using Adjacency List)

Let us apply BFS to the graph structure we introduced earlier.

from collections import deque

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

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

    while queue:
        node = queue.popleft()

        if node not in visited:
            print(node)
            visited.add(node)

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

bfs(graph, 'A')

This code explores the graph level by level, starting from node A.

Understanding the Execution Flow

Let us carefully walk through what happens:

• Start at A → visit A
• Visit neighbors B and C
• Then move to D

The output order reflects how BFS expands evenly instead of going deep immediately.

Time and Space Complexity

BFS runs in:

O(V + E)

Where:

• V = number of vertices
• E = number of edges

Every node and edge is visited at most once.

Common Mistakes in BFS

Beginners often make these mistakes:

• Forgetting to mark nodes as visited
• Using a stack instead of a queue
• Adding duplicate nodes to the queue

These errors can cause infinite loops or incorrect traversal.

Mini Practice

Imagine a graph representing flight routes.

If all flights have equal cost, which traversal strategy would help you find the shortest route?

Exercises

Quick Quiz

In the next lesson, we will explore Depth-First Search (DFS) and understand how it differs fundamentally from BFS.