Breadth-First Search (BFS)

What Is BFS?

Breadth-First Search is a graph traversal algorithm that visits all nodes at the current depth level before moving to the next. It uses a queue and guarantees the shortest path in an unweighted graph.

Algorithm Steps

1. Start at the source node and mark it as visited.
2. Add the source node to a queue.
3. Dequeue the front node and check its unvisited neighbors.
4. Mark each unvisited neighbor as visited and enqueue it.
5. Repeat until the queue is empty.

BFS Diagram

Learn More

Wikipedia page on Breadth-First Search