Breadth-First Search and Depth-First Search are the two fundamental ways to explore a graph — same underlying goal, genuinely different exploration order and genuinely different practical use cases.
from collections import deque
def bfs(graph, start):
visited, queue, order = {start}, deque([start]), []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
def dfs(graph, start, visited=None, order=None):
if visited is None:
visited, order = set(), []
visited.add(start)
order.append(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited, order)
return order
When to Use Which
- BFS — explores level by level using a queue; the natural choice for finding the shortest path in an unweighted graph, since it discovers closer nodes before farther ones
- DFS — explores as deep as possible before backtracking, using a stack (or recursion); natural for exploring all possibilities (maze solving, detecting cycles, topological sorting)
A common real-world example: BFS is exactly what powers “shortest number of connections” features on social networks, while DFS underlies dependency resolution in build systems, walking as deep into a dependency chain as needed before backtracking to the next branch.