Graphs: Representation & Traversal
The most general structure in this course, and the two traversal algorithms that unlock everything built on top of it
Introduction
Every tree from Lessons 7-12 was already a graph, just a restricted one: connected, with no cycles, and every node except the root having exactly one parent. A general graph drops all three restrictions. Nodes ("vertices") can connect to any number of others, connections ("edges") can form cycles, and the whole structure doesn't even need to be connected. That flexibility is exactly what makes graphs the right model for road networks, social connections, dependency chains, and web links, none of which fit a tree's rigid hierarchy.
Graph Terminology
A Small Undirected Graph
Figure 1: Arrows on both ends mark an undirected edge, A-B-D-C-A even forms a cycle
Representing a Graph
There's no single "graph" data type, almost every graph algorithm is written against one of two representations, and the right choice depends on how dense the graph is.
Adjacency List
Each vertex maps to the list of vertices it connects to:
graph: dict[str, list[str]] = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C", "E"],
"E": ["D"],
}Adjacency Matrix
A grid where cell [i][j] marks whether an edge connects vertex i and vertex j:
vertices = ["A", "B", "C", "D", "E"]
index = {v: i for i, v in enumerate(vertices)}
matrix = [[0] * len(vertices) for _ in range(len(vertices))]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
for u, v in edges:
matrix[index[u]][index[v]] = 1
matrix[index[v]][index[u]] = 1 # undirected: mark both directionsprint(matrix[index["A"]][index["B"]]) # A-B is an edge print(matrix[index["A"]][index["D"]]) # A-D is not
Expected Output:
1 0
| Adjacency List | Adjacency Matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| "Are u and v connected?" | O(degree of u) | O(1) |
| Best for | Sparse graphs (E much less than V²) | Dense graphs, or when O(1) edge lookups matter most |
Breadth-First Search (BFS)
This is exactly Lesson 7's level-order tree traversal, generalized: visit the start node, then everything one edge away, then everything two edges away, and so on. A graph has no single root and can have cycles, so BFS needs a visited set to avoid looping forever, something a tree traversal never had to worry about.
from collections import deque
def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
visited = {start}
order: list[str] = []
queue: deque[str] = deque([start]) # Lesson 4's queue, level by level
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 orderprint(bfs(graph, "A"))
Expected Output:
['A', 'B', 'C', 'D', 'E']
The number under each node is the order BFS reaches it, starting from A. It clears an entire level before going deeper, so B and C (both one hop from A) are visited before D:
BFS Visit Order from A
Figure 2: The queue drives level-by-level order: A, then everything one hop away (B, C), then two hops (D), then three (E).
BFS Finds the Shortest Path, for Free
Because BFS visits nodes in strict distance order, the first time it reaches any node is guaranteed to be via the fewest possible edges. In this graph, A is 0 hops away, B and C are 1, D is 2, and E is 3, exactly the order BFS produces. This is the entire basis for unweighted shortest-path search.
Depth-First Search (DFS)
Instead of exploring level by level, DFS commits to one path and follows it as far as possible before backtracking, exactly Lesson 7's preorder traversal, generalized the same way. The natural way to write it uses Lesson 5's call stack directly:
def dfs_recursive(
graph: dict[str, list[str]],
node: str,
visited: set[str] | None = None,
) -> list[str]:
if visited is None:
visited = set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(dfs_recursive(graph, neighbor, visited)) # Lesson 5's call stack
return orderDeep or cyclic graphs can risk hitting Python's recursion limit (Lesson 5 again), so an iterative version using an explicit stack is a common alternative:
def dfs_iterative(graph: dict[str, list[str]], start: str) -> list[str]:
visited = {start}
order: list[str] = []
stack = [start] # an explicit stack standing in for the call stack
while stack:
node = stack.pop()
order.append(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
return orderprint(dfs_recursive(graph, "A")) print(dfs_iterative(graph, "A"))
Expected Output:
['A', 'B', 'D', 'C', 'E'] ['A', 'B', 'D', 'E', 'C']
DFS commits to a path instead of fanning out. Following the recursive version from A, it dives A → B → D as far as it can before backtracking to pick up C, then finally E:
DFS Visit Order from A (recursive)
Figure 3: The call stack drives depth-first order: A, B, D reached going deep, then C on the way back, then E. Compare with the BFS order above.
Recursive and Iterative DFS Don't Always Match
Notice the two outputs above differ, C comes before E in one and after it in the other. Both are valid depth-first orders, every node is still visited exactly once, but the iterative version marks a node visited the moment it's pushed, while recursion effectively marks it on entry. That subtle difference can reorder siblings. If you need the exact same order as recursion, don't assume the iterative version gives it to you for free.
Practical Patterns: Components and Cycles
A single BFS or DFS call only reaches whatever is connected to its starting node. Running one from every not-yet-visited node finds every separate connected component:
def connected_components(graph: dict[str, list[str]]) -> list[list[str]]:
visited: set[str] = set()
components: list[list[str]] = []
for node in graph:
if node not in visited:
components.append(bfs_component(graph, node, visited))
return components
def bfs_component(graph: dict[str, list[str]], start: str, visited: set[str]) -> list[str]:
visited.add(start)
order: list[str] = []
queue = 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 orderdisconnected_graph = {
"A": ["B"], "B": ["A", "C"], "C": ["B"],
"X": ["Y"], "Y": ["X"],
}
print(connected_components(disconnected_graph))Expected Output:
[['A', 'B', 'C'], ['X', 'Y']]
The same "have I seen this before" tracking also detects cycles in an undirected graph: if a DFS ever reaches a node that's already visited and isn't the node it just came from, it found a loop.
def has_cycle(graph: dict[str, list[str]]) -> bool:
visited: set[str] = set()
def dfs(node: str, parent: str | None) -> bool:
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
# Reached an already-visited node that isn't where we came from
return True
return False
for node in graph:
if node not in visited:
if dfs(node, None):
return True
return Falseprint(has_cycle(graph)) # A-B-D-C-A is a cycle
tree_shaped = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A"], "D": ["B"]}
print(has_cycle(tree_shaped)) # a tree has no cycles by definitionExpected Output:
True False
neighbor != parent filters out that harmless case. A directed graph has no such symmetry: two separate edges can point into the same already-visited node without ever forming a cycle, so this exact technique reports false positives there. Detecting a cycle in a directed graph needs a different approach, tracking which nodes are still on the current DFS path, not just which nodes have been visited at all.Bonus: Counting Islands in a Grid
A 2D grid is a graph in disguise: every cell is a vertex, and it's connected to its up/down/left/right neighbors. Counting separate "islands" of connected "1" cells is just counting connected components on that implicit graph:
def num_islands(grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
visited: set[tuple[int, int]] = set()
def bfs(r: int, c: int) -> None:
queue = deque([(r, c)])
visited.add((r, c))
while queue:
row, col = queue.popleft()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = row + dr, col + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == "1" and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc))
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in visited:
islands += 1 # found a new island, BFS marks the rest of it visited
bfs(r, c)
return islandsgrid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"],
]
print(num_islands(grid))Expected Output:
3
No adjacency list is ever built, the neighbor relationship is computed on the fly from each cell's coordinates. This "implicit graph" pattern, rows and columns standing in for vertices and edges, shows up constantly in grid-based problems.
Key Takeaways
- A tree is a special case of a graph - connected, acyclic, one parent per node; graphs drop all three restrictions
- Adjacency lists suit sparse graphs, adjacency matrices suit dense ones or O(1) edge lookups
- BFS visits nodes in distance order, which is exactly why it finds shortest paths in unweighted graphs
- DFS explores one path fully before backtracking, and recursive vs iterative implementations aren't guaranteed to visit nodes in the same order
- Connected components and cycle detection both fall directly out of tracking which nodes a traversal has already visited