Algorithms · Lesson 11 of 17
Graph Traversal: BFS and DFS
Learn breadth-first search and depth-first search in Python: shortest paths in unweighted graphs, grid flood fill, connected components and cycle detection.
- Intermediate
- 18 min read
- 4 objectives
Before this lessonLesson 10: Dynamic Programming Patterns
What you will learn
- Implement BFS with a queue and DFS with recursion or a stack
- Use BFS to find shortest paths in unweighted graphs
- Traverse grids and count connected components
- Detect cycles in directed graphs with DFS colours
Your Progress
0 of 17 lessons 0%
- Lessons0 / 17
- Completed0
- Est. time left~ 5 hours
Create a free account to keep your progress on every device.
Tip: pressing Next marks this lesson complete automatically.
The Graphs lesson showed how to store a graph as an adjacency list. Almost every graph algorithm starts by visiting the nodes in some order, and there are two fundamental orders. Breadth-first search (BFS) explores in rings: all neighbours first, then their neighbours. Depth-first search (DFS) dives down one path as far as it can, then backs up and tries the next.
Both visit every node and edge once, so both cost O(V + E) time, where V is the number of vertices and E the number of edges. The difference is the order, and the order decides which problems each one solves well. We will use this small social graph of stackcone users throughout:
graph = {
"ada": ["bob", "cara"],
"bob": ["ada", "dev"],
"cara": ["ada", "dev", "eli"],
"dev": ["bob", "cara", "fay"],
"eli": ["cara"],
"fay": ["dev"],
}
print(len(graph), "users,", sum(len(v) for v in graph.values()) // 2, "friendships")6 users, 6 friendships
Breadth-first search
BFS uses a queue (first in, first out). Put the start node in, then repeatedly take the oldest node out and add its unvisited neighbours. Mark a node as visited when you add it, not when you pop it, or the same node can be queued many times.
# from earlier in this lesson
graph = {
"ada": ["bob", "cara"],
"bob": ["ada", "dev"],
"cara": ["ada", "dev", "eli"],
"dev": ["bob", "cara", "fay"],
"eli": ["cara"],
"fay": ["dev"],
}
# new code
from collections import deque
def bfs_order(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
return order
print(bfs_order(graph, "ada"))['ada', 'bob', 'cara', 'dev', 'eli', 'fay']
Use collections.deque, not a list: list.pop(0) is O(n) and would make BFS quadratic.
BFS gives shortest paths (when edges are unweighted)
Because BFS finishes every node at distance 1 before touching distance 2, the first time it reaches a node is along a path with the fewest edges. Record each node's parent and you can rebuild the path. This is how "degrees of separation" and fewest-hops routing work.
# from earlier in this lesson
from collections import deque
graph = {
"ada": ["bob", "cara"],
"bob": ["ada", "dev"],
"cara": ["ada", "dev", "eli"],
"dev": ["bob", "cara", "fay"],
"eli": ["cara"],
"fay": ["dev"],
}
# new code
def shortest_path(graph, start, goal):
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == goal:
path = []
while node is not None:
path.append(node)
node = parent[node]
return path[::-1]
for nxt in graph[node]:
if nxt not in parent:
parent[nxt] = node
queue.append(nxt)
return None
print(shortest_path(graph, "eli", "fay"))
print(shortest_path(graph, "ada", "ada"))['eli', 'cara', 'dev', 'fay'] ['ada']
Time O(V + E), space O(V) for the queue and parent map. If edges have different weights (road lengths, prices), BFS is no longer correct; you need Dijkstra, covered in the next lesson.
Depth-first search
DFS goes deep first. The recursive version is short because the call stack remembers where to come back to. An explicit stack version avoids Python's recursion limit (about 1,000 frames by default) on large graphs.
# from earlier in this lesson
graph = {
"ada": ["bob", "cara"],
"bob": ["ada", "dev"],
"cara": ["ada", "dev", "eli"],
"dev": ["bob", "cara", "fay"],
"eli": ["cara"],
"fay": ["dev"],
}
# new code
def dfs_recursive(graph, node, visited=None, order=None):
if visited is None:
visited, order = set(), []
visited.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in visited:
dfs_recursive(graph, nxt, visited, order)
return order
def dfs_iterative(graph, start):
visited, order, stack = set(), [], [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for nxt in reversed(graph[node]): # keep the same order as recursion
if nxt not in visited:
stack.append(nxt)
return order
print(dfs_recursive(graph, "ada"))
print(dfs_iterative(graph, "ada"))['ada', 'bob', 'dev', 'cara', 'eli', 'fay'] ['ada', 'bob', 'dev', 'cara', 'eli', 'fay']
Compare with BFS: DFS reached dev via bob before ever looking at cara. DFS does not find shortest paths, but it is the natural fit for questions about structure: is everything connected, is there a cycle, what order must tasks run in.
Grids are graphs too
A 2D grid is a graph where each cell connects to its up, down, left and right neighbours. Counting islands (groups of connected land cells) is a classic: scan every cell, and each time you find unvisited land, run a traversal to mark its whole island and add one to the count.
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
seen = set()
def flood(r, c):
stack = [(r, c)]
while stack:
r, c = stack.pop()
if (r, c) in seen or not (0 <= r < rows and 0 <= c < cols):
continue
if grid[r][c] != "#":
continue
seen.add((r, c))
stack.extend([(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)])
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "#" and (r, c) not in seen:
flood(r, c)
islands += 1
return islands
world = ["##..#",
"#...#",
"..#..",
".....",
"##.##"]
print(count_islands(world))5
Time O(rows * cols) because each cell is visited a constant number of times, space O(rows * cols) for the seen set. The same loop counts connected components in any graph.
Cycle detection in a directed graph
In a directed graph (like course prerequisites), a cycle means an impossible dependency. DFS with three colours detects it: white (unvisited), grey (on the current path), black (finished). Reaching a grey node means you walked back into your own path: a cycle.
def has_cycle(graph):
WHITE, GREY, BLACK = 0, 1, 2
color = {n: WHITE for n in graph}
def visit(n):
color[n] = GREY
for m in graph[n]:
if color[m] == GREY:
return True
if color[m] == WHITE and visit(m):
return True
color[n] = BLACK
return False
return any(color[n] == WHITE and visit(n) for n in graph)
ok = {"python": ["pandas"], "pandas": ["ml"], "ml": []}
bad = {"a": ["b"], "b": ["c"], "c": ["a"]}
print(has_cycle(ok), has_cycle(bad))False True
Recap
- BFS uses a queue and visits nodes in order of distance; DFS uses a stack or recursion and goes deep first.
- Both run in O(V + E) time and O(V) extra space.
- Mark nodes visited when you enqueue them to avoid duplicates.
- BFS finds shortest paths only when every edge has the same weight.
- Grids are graphs with four neighbours per cell; DFS with grey/black colours finds directed cycles.
# Write your solution here
Finished reading? Mark this lesson complete to track your progress.