BFS (Breadth-First Search) Traversal Explained

Breadth-First Search (BFS)

Breadth-First Search is one of the most fundamental graph traversal algorithms. It explores a graph by visiting all neighbors of the starting node before moving to the next level of neighbors, creating a "ripple effect" outward from the source.

How BFS Works

1. Initialize — Place the starting node into a queue and mark it as visited.
2. Dequeue — Remove the front node from the queue. This is the current node.
3. Explore neighbors — For each unvisited neighbor of the current node, mark it as visited and enqueue it.
4. Repeat — Continue until the queue is empty.

Queue: [A]           → Visit A, enqueue B, C
Queue: [B, C]        → Visit B, enqueue D
Queue: [C, D]        → Visit C, enqueue E
Queue: [D, E]        → Visit D
Queue: [E]           → Visit E
Queue: []            → Done

Time and Space Complexity

• Time: O(V + E) where V is the number of vertices and E is the number of edges
• Space: O(V) for the visited set and the queue

Key Properties

BFS guarantees the shortest path in an unweighted graph because it explores nodes in order of their distance from the source. Every node at distance d is visited before any node at distance d+1.

Level-Order Coloring

When visualizing BFS, nodes are often colored by their "level" — the distance from the source node. This makes it easy to see how the algorithm expands outward ring by ring.

BFS vs DFS

While BFS uses a queue (FIFO), DFS uses a stack (LIFO or recursion). BFS finds shortest paths in unweighted graphs; DFS is better for tasks like cycle detection and topological sorting.