A+DS

Breadth-First Search

Explore layer by layer, like ripples in a pond.

Drop a stone in a pond and watch the ripples spread outward in circles. BFS explores a graph the same way: first visit the start node, then all its neighbors, then all their neighbors, and so on. It uses a queue (first-in, first-out) to ensure level-by-level exploration.

     [ START ]         layer 0
      / | \
    [A] [B] [C]        layer 1
    / \    |
  [D] [E] [F]          layer 2

  Queue: [START] → [A,B,C] → [D,E,F]

How it works

  1. 1Start at the source node, add it to a queue
  2. 2Dequeue the front node and visit it
  3. 3Enqueue all unvisited neighbors
  4. 4Repeat until the queue is empty

Loading...