Trees & GraphsMedium

BFS

Visit nodes level-by-level using a queue to find shortest paths.

How it works

Breadth-First Search explores a graph level by level — it visits all neighbors of the current node before going deeper. A queue (FIFO) is the key data structure: enqueue the start node, then repeatedly dequeue a node, process it, and enqueue its unvisited neighbors. BFS guarantees the shortest path (minimum edges) in an unweighted graph because it explores all paths of length 1 before any path of length 2. For weighted graphs, use Dijkstra instead. Multi-source BFS (start from multiple nodes simultaneously) is useful for problems like "distance to nearest 0" or "rotting oranges." Use a visited set to avoid processing the same node twice.

Interactive Playground

Add node 1 to queue. Level 0 begins.

Speed

When to use

Shortest path in an unweighted graph
Level-order tree traversal
Finding connected components at minimum distance

✅Tips

1Mark nodes as visited when you enqueue them, not when you dequeue — prevents adding the same node to the queue multiple times.

2For level-by-level processing, snapshot the queue size at the start of each level: `for i in range(len(queue))`.

3Multi-source BFS: add all source nodes to the queue before starting — they all start at distance 0.

4For grid problems, use a directions array `[(0,1),(0,-1),(1,0),(-1,0)]` for neighbor generation.

❌Common Mistakes

!Marking visited when dequeuing instead of when enqueuing — causes the same node to be added many times, inflating the queue.

!Forgetting to mark the starting node as visited before the loop begins.

!Using a list as a queue in Python (pop(0) is O(n)) — use `collections.deque` for O(1) popleft.

!Not handling disconnected graphs — run BFS from each unvisited node to cover all components.

💡 Key Insight:BFS guarantees shortest path in unweighted graphs — DFS does not.

Solved Problems0

No solved problems yet.

Related Patterns

DFS→Tree Traversal→