Module 5 Graph Search 19

BFS — Breadth-First Search (Queue + Levels)

BFS explores a graph in “waves” from a source. In an unweighted graph, BFS gives the shortest path (fewest edges) to every node. Click a node to set source. Optional: set a target to show the shortest path.

V 6 · E 7 Source 0 Target — Step 0

Directed Show BFS tree edges Click sets target (else sets source)

Auto

Speed

Legend: yellow = current “dequeue” node, green = visited, purple = discovered (in queue), blue/orange edge = the neighbor being checked. If target is set, the final path is highlighted.

Vertices (V)

u (edge from)

v (edge to)

Queue front → back

Levels distance from source (BFS “waves”)

Start BFS to see levels…

Shortest path (if target selected): —

Unweighted shortest path BFS levels = distance Time O(V + E)

In BFS, when we first discover a node, we set parent[v] = u. That parent pointer forms the BFS tree, and lets us reconstruct shortest paths.

📌 BFS Summary ▸

Next: 20 — DFS (stack/recursion + traversal tree). BFS is queue-based; DFS is stack-based.