Think together · Start with a little story
The robot is looking for a flag in a tree house. It can follow one path all the way in, or check every nearby room first.
Lay out the process
- DFSGo deep, then return
- BFSNearby layers, then farther ones
- Tools for keeping trackStack and queue
- Choose for the problemDo you need the fewest steps?
The main difference between DFS and BFS is the order in which they explore.
Both can check reachability; BFS is commonly used for shortest paths in an unweighted graph. DFS often suits branching exploration. Whether it uses less memory depends on the graph’s shape.
01What is their biggest difference?
DFS
Follow one path as deeply as possible first.
BFS
Finish exploring everything at the same distance first.
02What data structure does each one use?
DFS
Recursive call stack or an explicit stack.
BFS
A queue.
03Which one finds a shortest path?
In an unweighted graph:
- BFS can guarantee a path with the fewest edges.
- The first path found by ordinary DFS is not guaranteed to be the shortest.
04Which one uses less memory?
There is no universal answer.
DFS needs to store the current path and related state. BFS may need to keep an entire layer—or many waiting nodes—in memory at once.
05Do they have the same time complexity?
With an adjacency list, if each node and edge is handled only a constant number of times, traversing a general graph with DFS or BFS is usually:
V is the number of vertices, and E is the number of edges.
06When is DFS a better fit?
- When you need to explore deeply and backtrack.
- For recursive tree structures.
- For finding connected components.
- As a foundation for many graph algorithms, including topological sorting, bridges, and articulation points.
07When is BFS a better fit?
- For shortest paths in an unweighted graph.
- For level-order traversal.
- For expanding layer by layer according to distance.
- For shortest-step searches from multiple starting points.
What have you learned?
- DFS prioritizes depth; BFS prioritizes layers.
- DFS commonly uses a stack, while BFS commonly uses a queue.
- BFS is usually used for shortest paths in an unweighted graph.
- Both usually take O(V + E) to traverse a graph represented by an adjacency list.
- Which one uses less memory depends on the graph and implementation.
Next: Why Do Some Programs Finish in a Second While Others Take Much Longer?
Your turn to try
The target is right beside the start, but DFS first chooses a very long path. What might happen?
Ready? Open to see the explanation
DFS might take a long time to return and check the nearby target. BFS checks every position one step away first.