Graph Traversal

Chapter 1: Flavors of Graphs

Graphs come in many varieties, and the flavor matters for which algorithms apply:

A simple graph has no self-loops (edge from a vertex to itself) and no multi-edges (multiple edges between the same pair). Most algorithms assume simple graphs unless stated otherwise.

Chapter 2: Graph Representations

How do you store a graph in a computer? Two approaches dominate:

An adjacency matrix is an n × n grid M where M[i][j] = 1 if there's an edge from vertex i to j. Fast to check if an edge exists (O(1)), but uses O(n²) space regardless of how many edges there are.

An adjacency list stores, for each vertex, a linked list of its neighbors. Uses O(n + m) space (n vertices, m edges). Traversal is efficient because you only visit actual edges. But testing whether a specific edge exists requires scanning a list.

Chapter 3: Breadth-First Search

Breadth-first search (BFS) explores a graph level by level, like ripples spreading from a stone dropped in a pond. It visits all vertices at distance 1, then distance 2, then distance 3, and so on.

BFS uses a queue (FIFO). Start from a source vertex s, mark it discovered, and enqueue it. Then repeat: dequeue a vertex, explore all its undiscovered neighbors, mark and enqueue them. When the queue is empty, you've visited everything reachable from s.

python
def bfs(graph, start):
    discovered = {start}
    queue = [start]
    parent = {start: None}
    while queue:
        v = queue.pop(0)  # dequeue front
        for neighbor in graph[v]:
            if neighbor not in discovered:
                discovered.add(neighbor)
                parent[neighbor] = v
                queue.append(neighbor)
    return parent

BFS runs in O(n + m) time: each vertex is enqueued once, and each edge is examined once. This is optimal -- you can't do better than looking at the whole graph.

Chapter 4: BFS Applications

BFS is not just a traversal -- it's a problem-solving tool. Here are the key applications that fall out of BFS almost for free:

Connected components: In an undirected graph, a connected component is a maximal set of vertices reachable from each other. Run BFS from any unvisited vertex -- everything it reaches forms one component. Repeat until all vertices are visited. Each BFS call discovers one component.

Two-coloring (bipartiteness): Can you color every vertex red or blue such that no edge connects two vertices of the same color? BFS can test this: color the source red, all its neighbors blue, all their neighbors red, etc. If you ever find an edge between same-colored vertices, the graph is not bipartite.

Shortest path tree: The parent pointers from BFS form a tree rooted at the source. Following parents from any vertex back to the source traces the shortest path. This tree is the BFS tree.

Chapter 5: Depth-First Search

Depth-first search (DFS) is the other fundamental traversal. Instead of exploring level-by-level, it dives as deep as possible along each branch before backtracking. Think of it as exploring a maze by always turning left until you hit a dead end, then backtracking.

DFS uses a stack (LIFO) -- either explicitly or via the call stack of recursion. The recursive version is elegant:

python
def dfs(graph, v, discovered, parent):
    discovered.add(v)
    for neighbor in graph[v]:
        if neighbor not in discovered:
            parent[neighbor] = v
            dfs(graph, neighbor, discovered, parent)

DFS classifies every edge in the graph into one of four types:

Chapter 6: DFS Applications

DFS powers several important graph algorithms that BFS cannot easily do:

Topological sorting: Given a DAG (directed acyclic graph), produce an ordering of vertices such that for every directed edge (u, v), u appears before v. Think of it as a valid ordering of tasks respecting all dependencies. DFS gives us topological order by reverse finishing time: process a vertex only after all its descendants are finished.

Articulation points (cut vertices): A vertex whose removal disconnects the graph. These are critical points of failure in a network. DFS can find all articulation points in O(n + m) time using entry times and low-link values.

Strongly connected components: In a directed graph, a strongly connected component is a maximal set of vertices where every vertex is reachable from every other. DFS on the graph and its reverse (Kosaraju's algorithm) finds all SCCs in O(n + m) time.

Chapter 7: The Graph Explorer

Time to watch BFS and DFS explore the same graph side by side. Notice how they visit vertices in completely different orders and produce different tree shapes.

Chapter 8: Connections

Graph traversal is the foundation for everything in the next four chapters: