PYTHON & CODING · QUESTION 86
What is the difference between breadth-first and depth-first search?
On this page
Breadth-first search (BFS) explores a graph level by level using a queue; on an unweighted graph, it finds a shortest path in number of edges. Depth-first search (DFS) follows one branch deeply before backtracking, using a stack or recursion. Both run in O(V + E) with adjacency lists, but suit different goals and memory patterns.
LET'S MAKE IT SIMPLE
First, the idea in plain English
A graph contains nodes connected by edges. BFS first visits immediate neighbors, then neighbors of those neighbors. DFS follows one route as far as it can, then returns to explore another. Both need a visited set to avoid repeating work or getting stuck in cycles.
A USEFUL COMPARISON
Picture it this way
BFS searches a building floor by floor, checking nearby rooms before farther ones. DFS walks one hallway until it ends, then backtracks. The first strategy finds the fewest doors in an unweighted layout; the second can reach deep destinations with a stack.
FOLLOW THE JOURNEY
Queues explore levels; stacks explore one branch at a time
Compare traversal order and shortest-path behavior.
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; Each edge and vertex is processed a bounded number of times.
A graph traversal shows BFS visiting all neighbors at each distance using a queue, while DFS follows one path with a stack before backtracking.
How to read this visual
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; Each edge and vertex is processed a bounded number of times.
UNDER THE HOOD
How it works, step by step
Track visited nodes
Mark nodes when they are discovered.
Why it matters: A visited set prevents cycles and duplicate processing.
Choose frontier structure
Use a queue for BFS or a stack/recursion for DFS.
Why it matters: The frontier determines which node is explored next.
Visit neighbors
Add unvisited adjacent nodes and continue until the goal or graph ends.
Why it matters: Each edge and vertex is processed a bounded number of times.
OUTSIDE THE TEXTBOOK
A practical example
For the fewest number of train stops between two stations, BFS finds a shortest path when each stop counts equally. DFS can be useful for checking whether any route exists or exploring connected components, but its first route is not guaranteed to use the fewest edges.
GO A LITTLE DEEPER
Technical details that matter
- With adjacency lists, traversal takes O(V + E) time and O(V) auxiliary space.
- BFS shortest-path guarantees require equal edge costs; weighted shortest paths need algorithms such as Dijkstra’s under suitable conditions.
- Recursive DFS can exceed Python’s recursion limit on deep graphs; an explicit stack avoids that call-stack issue.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visitedThe queue preserves discovery order by distance. The visited set is updated when a neighbor is enqueued, preventing duplicate queue entries.
MAKE A GOOD CHOICE
When is this useful?
- BFS for unweighted shortest paths and level-order traversal.
- DFS for connected components, cycle detection, and backtracking.
- Traversing dependency graphs or state spaces.
Use Dijkstra’s algorithm for nonnegative weighted shortest paths. Use topological sorting for dependency ordering in a directed acyclic graph.
WATCH OUT FOR
Common misunderstandings
- Using DFS when a shortest unweighted path is required.
- Marking nodes too late and enqueueing duplicates.
- Ignoring recursion depth on deep Python graphs.
REAL-WORLD TRADE-OFFS
Limitations and failure cases
- BFS can use substantial memory for wide graphs.
- DFS traversal order depends on neighbor ordering.
- Graph representation affects practical performance.
WHAT TO REMEMBER
Key takeaways
- 1BFS uses a queue and explores by distance.
- 2DFS uses a stack or recursion and explores deeply.
- 3Both need visited tracking; BFS gives shortest paths only in unweighted graphs.
PRACTICE THE FOLLOW-UP
What might an interviewer ask next?
Why does BFS find an unweighted shortest path?
It visits nodes in increasing number of edges from the start, so the first discovery of a node has the fewest edges.
When would DFS recursion be risky in Python?
On very deep graphs it can exceed the interpreter recursion limit; an explicit stack avoids using the call stack for every node.
SAY IT OUT LOUD
How to explain this in an interview
“BFS explores a graph level by level using a queue, so it finds a shortest path in edge count when edges are unweighted. DFS uses a stack or recursion to follow one branch and backtrack. Both are O(V plus E) with adjacency lists and need a visited set. I choose based on shortest-path requirements and memory shape.”
Connect this question to the roadmap topic it supports.