Graph Traversal — BFS and DFS Explained Visually
graph-algorithms not found in registry.What Is Graph Traversal?
Graph traversal means visiting every node in a graph by following edges. Google Maps finding routes, Instagram suggesting friends, file explorers opening folders — all graph traversal.
There are two fundamental strategies: BFS and DFS. Every other graph algorithm builds on one of these.
Breadth-First Search (BFS)
Imagine ripples spreading from a stone dropped in a pond. BFS explores level by level using a queue (FIFO). It visits all immediate neighbours first, then distance-2 nodes, then distance-3, and so on.
Because of this level-order property, BFS guarantees the shortest path in unweighted graphs.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "E"],
"D": ["B", "F"],
"E": ["B", "C", "F"],
"F": ["D", "E"]
}
print("BFS:", bfs(graph, "A"))Depth-First Search (DFS)
Like exploring a maze — go as deep as possible, then backtrack. DFS uses a stack (LIFO) or recursion. It is the backbone of cycle detection, topological sort, and backtracking algorithms.
def dfs(graph, start):
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
order.append(node)
for neighbour in reversed(graph[node]):
if neighbour not in visited:
stack.append(neighbour)
return order
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "E"],
"D": ["B", "F"],
"E": ["B", "C", "F"],
"F": ["D", "E"]
}
print("DFS:", dfs(graph, "A"))| Property | BFS | DFS |
|---|---|---|
| Data structure | Queue (FIFO) | Stack (LIFO) |
| Order | Level by level | Deep first, backtrack |
| Shortest path? | Yes (unweighted) | No |
| Time | O(V + E) | O(V + E) |
| Space | O(V) | O(V) |
| Best for | Shortest path, level-order | Cycle detection, topological sort |
Key Takeaways
- BFS uses a queue, explores level by level, guarantees shortest path in unweighted graphs.
- DFS uses a stack or recursion, goes deep before backtracking.
- Both run in O(V + E) time.
- Always mark nodes visited to avoid infinite loops.
- Next up: Dijkstra’s Algorithm for weighted shortest paths.