Breadth-First and Depth-First Search
Two ways to visit every node reachable from a start point: one takes a queue and spreads out level by level, the other takes a stack and follows one path as far as it goes. The choice of structure is the whole difference between them.
What a learner can do afterwards
- Give the visit order both searches produce on the same graph from the same start
- Explain why swapping the queue for a stack turns one search into the other
- Say why visited nodes must be recorded, and what happens on a cycle if they are not
1 · Read
Breadth first search spreads level by level using a queue. You visit every neighbour of the start before stepping further out, so the first time you reach a node you arrived by the fewest hops. That makes it the route finder for unweighted graphs.
You run the queue by taking its front, visiting unvisited neighbours, and joining them to the back. The queue forces level order. Swap the queue for a stack and the walk turns into depth first search: you dive down one path as far as it goes and backtrack only when stuck.
You always keep a visited record beside the waiting line. Each vertex and edge is then handled once, which costs order V plus E. Without the record, a cycle sends the search around forever, queueing the same nodes again and again.
You usually store the graph as adjacency lists pairing each node with neighbours, which stays compact on sparse graphs. When asked for the fewest hops route, you reach for breadth first search, not depth first.
Queues spread in waves for fewest hops, stacks dive deep, and visited records stop cycles.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.