BFS in Graphs

In Graph BFS, we want to traverse a graph layer-by-layer starting from a source node. Unlike trees, graphs can have cycles (A->B->A), disconnected components, and multiple paths to the same node.

Goal:

1. Given an unweighted graph, find the shortest path (minimum edges) from start to target.
2. Visit all nodes reachable from start.

Using the Queue (FIFO) structure:

1. Queue: Stores nodes to visit next. Initialize with [start].
2. Visited Set: Crucial! Marks nodes as 'seen' to prevent infinite loops in cycles. Add start to visited immediately.
3. Loop: While Queue is not empty:
   • Dequeue node U.
   • For every neighbor V of U:
     • If V is not in visited, add it to visited and Enqueue V.

This guarantees that we process nodes in order of their distance: Distance 0 (start), then Distance 1 (neighbors), then Distance 2, etc.

Watch how BFS explores widely (expanding rings), finding the shortest path to any node.