Breadth-First Search (BFS)

Explore graphs level-by-level using a FIFO queue.

Traversal Style

Level-Order

Expands frontier layer by layer

Shortest Paths

Yes (Unweighted)

First discovery gives min edge count

Data Structure

Queue

FIFO ensures level ordering

When to Use BFS

Finding shortest path in unweighted graphs
Checking bipartiteness
Level-order traversal in trees
Finding connected components (with repeated BFS)
Web crawler / friend-of-friend expansions

Core Idea

Maintain a queue of the current frontier. Dequeue a node, process it, and enqueue all undiscovered neighbors. Mark nodes when enqueued to avoid duplicates. Track distance by storing level = parent level + 1.

Algorithm Metrics

Time

O(V + E)

Space

O(V)

Shortest Path

Yes

Traversal

Layered

Back: Graph Algorithms Next: DFS