Breadth First Search (BFS): A Comprehensive Guide

3 min readJul 14, 2024

Breadth First Search (BFS) is a fundamental algorithm for traversing or searching through tree or graph data structures. Unlike Depth First Search (DFS), which explores as far as possible along each branch before backtracking, BFS explores all neighbors at the present depth prior to moving on to nodes at the next depth level. BFS utilizes a queue data structure, operating on the FIFO (first in, first out) principle.

Working Principle:

Starting Point:

Select a starting node (e.g., node A). This node will be the root of our search.

2. Traversal Method:

Enqueue the starting node and mark it as visited.
Dequeue a node from the front of the queue, process it, and enqueue all its unvisited neighbors.

3. Simultaneous Exploration:

Unlike DFS, BFS enqueues all neighbors of the current node at once.
This ensures that nodes are explored level by level, providing the shortest path in unweighted graphs.

4. Completion:

The process continues until all nodes have been visited, ensuring the traversal covers the entire graph.

Example Execution:

Starting at Node A:

Neighbors of A: Nodes B and D are directly reachable.
Enqueue A, then enqueue its neighbors B and D. The queue becomes [A, B, D]. Dequeue A as it is processed.

From Nodes B and D:

Dequeue B and process its neighbors.
Neighbors of B: Node C is discovered. Enqueue C. The queue now is [B, D, C].
Dequeue D and process its neighbors.
Neighbors of D: Nodes E and F are discovered. Enqueue E and F. The queue becomes [D, C, E, F].

Key Considerations:

Each node must be visited exactly once.
Upon completing the traversal, all nodes will have been visited in order of their distance from the starting node.

By following this approach, BFS ensures that every node in the graph is visited once and only once, providing a systematic method for exploring the entirety of the structure.

Python Implementation of BFS

The graph is represented as an adjacency list, a dictionary where each key is a node and the corresponding value is a list of its neighbors.

# Define the graph as an adjacency list
graph = {
    'A': ['B', 'D'],
    'B': ['C'],
    'C': ['E', 'F'],
    'D': ['E'],
    'E': [],
    'F': []
}

# Define the BFS function
def bfs(graph, start):
    # Create an empty queue and enqueue the start node
    queue = [start]
    # Create a set to keep track of visited nodes
    visited = set(start)

    # Loop until there are nodes to process
    while queue:
        # Dequeue a node from the front of the queue
        node = queue.pop(0)
        print(node, end=' ')  # Print the node (or process it in any other way)

        # Enqueue all unvisited neighbors
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Call the BFS function starting from node 'A'
bfs(graph, 'A')

queue: A list that serves as the queue to manage the nodes to visit. The search starts by enqueuing the starting node.
visited: A set to keep track of visited nodes to ensure each node is processed only once.

Loop: