Lesson 099
Breadth-First Search
Level Order · Queue · Shortest Path
1:00How BFS uses a FIFO queue to explore a graph level by level, guaranteeing shortest paths in unweighted graphs.
By the end, you can
- Explain why a FIFO queue causes BFS to explore a graph level by level.
- Trace BFS on a small graph, maintaining the queue and visited set by hand.
- Compute the BFS distance from a source to any node.
- State why BFS gives the shortest path only in unweighted graphs, and name the algorithm (Dijkstra) needed once edges carry weights.
- Describe the "mark on enqueue" rule and explain what goes wrong if it is deferred to dequeue time (the same node gets enqueued several times, wasting work and breaking the distance guarantee).
- Give the time and space complexity of BFS and justify both bounds.
- Decide whether BFS or DFS is more appropriate for a given graph problem.
Up next in Searching & Sorting
