Graph Traversal Concepts

Graph traversal means visiting every vertex reachable from a starting point, each exactly once, by following edges. Maps, social networks, task dependencies and mazes are all questions of "what is connected to what", and most of them are solved with a traversal. This chapter covers the vocabulary, how to store a graph in code, and the intuition behind the two classic traversals: breadth-first search (BFS) and depth-first search (DFS).

Vocabulary

By convention V is the number of vertices and E the number of edges. Graph algorithm costs are almost always written in terms of these two.

Storing a graph

The default choice is an adjacency list: each vertex keeps a list of its neighbors. It uses O(V + E) memory, and iterating over a vertex's neighbors costs only as much as it has neighbors.

from collections import defaultdict

edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected: add the reverse edge too

print(graph[2])  # [0, 3, 4]

An adjacency matrix is a V x V table of 0s and 1s. It answers "is there an edge between u and v?" in O(1), but needs O(V^2) memory, which is wasteful for sparse graphs with many vertices and few edges.

n = 6
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
    matrix[u][v] = matrix[v][u] = 1

print(matrix[2][4] == 1)  # True: 2 and 4 are neighbors

A plain edge list (the edges variable itself) is also a representation. It suits algorithms that sort edges, such as Kruskal's, but finding neighbors means scanning everything, so for traversal you convert it into an adjacency list first.

Directions and vertex ids

For a directed graph, add only u→v. When vertices are strings (city names, module names), either use a dictionary or map each name to an integer id and use a list of lists, which is faster and lighter. If the input numbers vertices from 1, size your lists n + 1 or subtract 1 from every id to avoid index errors.

names = ["core", "ui", "app"]
index = {name: i for i, name in enumerate(names)}
adj = [[] for _ in names]
for before, after in [("core", "ui"), ("ui", "app")]:
    adj[index[before]].append(index[after])   # one direction only

print(adj)  # [[1], [2], []]

Grids are graphs too

Mazes and maps given as 2D grids become graphs once you treat each cell as a vertex and connect cells that touch up, down, left or right. These are usually handled as implicit graphs: instead of building an adjacency list, you compute neighbors on the fly.

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def neighbors(grid, r, c):
    rows, cols = len(grid), len(grid[0])
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
            yield nr, nc

BFS and DFS in one picture

• BFS (breadth-first search) expands outward one layer at a time, nearest vertices first, using a queue. In a graph where every edge has the same cost, it finds shortest paths (fewest edges).
• DFS (depth-first search) goes as deep as it can along one branch, then backtracks, using recursion or an explicit stack. It is the backbone of connected components, cycle detection, topological sorting and backtracking.

Both depend on a visited marker. Never revisiting a vertex is what makes traversal terminate on graphs with cycles and keeps the total cost at O(V + E).

Which one to use

Summary

A graph models relationships with vertices and edges, and traversal follows edges while marking what it has seen. An adjacency list is the default representation, and grids are best treated as implicit graphs. BFS, which grows outward layer by layer, gives unweighted shortest distances; DFS, which dives deep first, is the tool for structure: components, cycles and topological order.