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.
More to read
Breadth-first search and its uses
Breadth-first search explores a graph in waves, visiting every neighbour of the start before moving one step further out. That wave order makes it perfect for shortest paths on unweighted graphs and for anything that spreads level by level. Read where the method gets used, from route finding to network crawling. Each use leans on the same promise: the first time BFS reaches a node, it arrived by a shortest route.
The breadth-first search algorithm
The algorithm keeps a queue of places to visit and a record of places seen. Take the front of the queue, visit its unvisited neighbours, and join them to the back of the line. The queue is what forces the level by level order. Trace it on a small graph from a fixed start and write down the visit order. Then swap the queue for a stack in your head and watch depth-first search emerge, diving down one path before trying the next.
Analysis of breadth-first search
This article counts the cost: each vertex and each edge is handled once, giving O(V + E) time. That linear bill explains why BFS scales to huge graphs. It also shows why the visited record matters. Without it, a cycle would send the search around forever, revisiting the same nodes without end.
Representing graphs
Before you can search a graph, you must store it. The usual choices are adjacency lists, which note the neighbours of each node, and adjacency matrices, which tick a grid of connections. Lists win on sparse graphs, while matrices answer edge questions instantly. Learn both layouts and pick lists as your default for search. The queue and visited set sit on top of this storage, so a clear picture of the layout makes every trace easier.
2 · Watch
Take it off screen
Where it sits
This opens up
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.