A Breadth-First Search

An application for using queues.

Breadth-First Search (BFS) – Step-by-Step Description

1. Initialization
   • Create an array dist to store the shortest distance from the source node to every other node.
   • Set every entry in dist to a very large value (∞) to mean “unvisited”.
   • Create an empty queue Q.
   • Set dist[source] = 0 because the source is distance 0 from itself.
   • Place the source node into the queue.
2. Iterative Exploration
   • While the queue is not empty:
     1. Remove (dequeue) the front node—call it u.
     2. Look at every neighbor v of u.
     3. If v has not yet been visited (dist[v] is still ∞):
        • Set dist[v] = dist[u] + 1 (one hop farther than u).
        • Enqueue v to explore its neighbors later.
3. Completion
   • When the queue is empty, every reachable vertex has been visited and its shortest distance from the source is stored in dist.