BFS — Explained with Examples

BFS (Breadth-First Search) is a graph traversal algorithm that explores all neighbors at the current depth before moving to the next level.

BFS uses a queue to track nodes to visit. Starting from a root node, it visits all direct neighbors first, then their unvisited neighbors, level by level. BFS guarantees finding the shortest path in unweighted graphs. Time complexity is O(V + E) where V is vertices and E is edges. Space complexity is O(V) in the worst case.

Think of BFS like dropping a stone in a pond. Ripples expand outward in concentric circles. The stone hits the closest lily pads first, then the next ring, then the next. If you’re looking for the nearest lily pad, the first ripple will find it.

BFS is used for shortest path in unweighted graphs, web crawling, social network friend suggestions (degrees of separation), and finding connected components.

from collections import deque

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

    while queue:
        node = queue.popleft()
        print(node, end=" ")

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

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

bfs(graph, 'A')  # Output: A B C D E F

BFS is ideal when the target is likely near the source, or when level-order traversal is needed. For deep graphs, DFS may be more memory-efficient.

DFS, Graph, Tree, Queue

DFS Comparison