Graph Representation and Traversal

Chapter 16: Graph Representation and Traversal

In previous chapters, we studied various linear and hierarchical structures — arrays, linked lists, trees. These structures share a common trait: their connectivity is "regular." Each array element has a predecessor and successor; each tree node has one parent and some children. But in the real world, many relationships are far more complex — friendships in a social network are many-to-many, road networks between cities are interwoven, and web pages on the internet point to each other through hyperlinks.

The graph is the ultimate data structure for describing these complex relationships. It consists of vertices (nodes) and edges, and can express relationships between any pair of entities. Graph theory is not only fundamental to computer science but also one of the most fruitful branches of discrete mathematics.

This chapter addresses three core questions: (1) How do we efficiently represent a graph in a computer? (2) How do we systematically visit every vertex in a graph? (3) What structural information about the graph can traversal reveal?

Level 1 · What You Need to Know

16.1 Basic Graph Concepts

Definition: A graph G = (V, E), where V is a set of vertices and E is a set of edges. Each edge connects two vertices.

Based on whether edges have direction, graphs fall into two categories:

• Undirected Graph: Edges have no direction; (u, v) and (v, u) are the same edge. Example: Facebook friendships (mutual).
• Directed Graph (Digraph): Edges have direction; an edge from u to v is written (u, v), and u→v differs from v→u. Example: Twitter follows (A follows B doesn't mean B follows A).

Key terminology:

Undirected graph (social network):    Directed graph (web links):
  A --- B                              A → B
  |   / |                              ↑   ↓
  |  /  |                              D ← C
  C --- D

Undirected: edges have no arrows     Directed: edges have direction
A-B means A and B are mutual friends  A→B means A links to B

16.2 Two Ways to Store a Graph

There are two classic ways to represent a graph in a computer: adjacency matrix and adjacency list.

16.2.1 Adjacency Matrix

Use a |V|×|V| 2D array matrix. matrix[i][j] = 1 (or a weight) means there is an edge from vertex i to vertex j; matrix[i][j] = 0 means no edge.

class GraphMatrix:
    """Graph representation using adjacency matrix"""
    
    def __init__(self, num_vertices: int, directed: bool = False):
        self.n = num_vertices
        self.directed = directed
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, u: int, v: int, weight: int = 1):
        """Add edge u → v"""
        self.matrix[u][v] = weight
        if not self.directed:
            self.matrix[v][u] = weight
    
    def has_edge(self, u: int, v: int) -> bool:
        """Query edge existence — O(1)"""
        return self.matrix[u][v] != 0
    
    def get_neighbors(self, u: int) -> list:
        """Get all neighbors — O(V)"""
        neighbors = []
        for v in range(self.n):
            if self.matrix[u][v] != 0:
                neighbors.append(v)
        return neighbors
    
    def degree(self, u: int) -> int:
        """Vertex degree"""
        return sum(1 for v in range(self.n) if self.matrix[u][v] != 0)


# Example: create an undirected graph
#   0 --- 1
#   |   / |
#   |  /  |
#   2 --- 3
g = GraphMatrix(4, directed=False)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print(g.has_edge(0, 1))  # True
print(g.has_edge(0, 3))  # False
print(g.get_neighbors(1))  # [0, 2, 3]

Adjacency matrix characteristics:

Pros: Extremely fast edge queries (O(1) random access); simple implementation.

Cons: O(V²) space — very wasteful for sparse graphs (far fewer edges than V²).

16.2.2 Adjacency List

For each vertex, maintain a list of all adjacent vertices. This is the most common representation in practice.

from collections import defaultdict

class GraphList:
    """Graph representation using adjacency list"""
    
    def __init__(self, directed: bool = False):
        self.directed = directed
        self.adj = defaultdict(list)
    
    def add_edge(self, u, v, weight=1):
        """Add edge u → v"""
        self.adj[u].append((v, weight))
        if not self.directed:
            self.adj[v].append((u, weight))
    
    def has_edge(self, u, v) -> bool:
        """Query edge existence — O(degree(u))"""
        return any(neighbor == v for neighbor, _ in self.adj[u])
    
    def get_neighbors(self, u) -> list:
        """Get all neighbors — O(degree(u))"""
        return [v for v, _ in self.adj[u]]
    
    def degree(self, u) -> int:
        """Vertex degree"""
        return len(self.adj[u])
    
    def vertices(self) -> set:
        """All vertices"""
        return set(self.adj.keys())


# Example: same graph using adjacency list
g = GraphList(directed=False)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print(g.get_neighbors(1))  # [0, 2, 3]
print(g.degree(1))  # 3

Adjacency list characteristics:

Pros: Space-efficient (only stores actual edges); fast neighbor traversal.

Cons: Edge queries slower than adjacency matrix.

16.2.3 How to Choose?

Key intuition: Most real-world graphs are sparse. Social networks have billions of users but each person averages only a few hundred friends; the internet has billions of pages but each page links to a limited number of others. Therefore, the adjacency list is the default choice in engineering.

16.3 Breadth-First Search (BFS)

BFS starts from a source vertex and visits all vertices at distance 1 first, then all at distance 2, and so on — spreading outward like ripples on water.

Core idea: Use a queue (FIFO). Dequeue a vertex, enqueue all its unvisited neighbors.

from collections import deque

def bfs(graph: GraphList, start) -> list:
    """
    Breadth-First Search
    Returns visit order
    """
    visited = set()
    order = []
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        order.append(node)
        
        for neighbor in graph.get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return order


# Example
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)

print(bfs(g, 0))  # [0, 1, 2, 3, 4]

Key properties of BFS:

1. Level-order traversal: BFS visits vertices layer by layer, by distance from the source.
2. Shortest path (unweighted): When BFS first reaches a vertex, the number of edges traversed equals the shortest path length from the source.
3. Time complexity: O(V + E) — each vertex is enqueued/dequeued once, each edge is examined once.
4. Space complexity: O(V) — the visited set and queue hold at most V vertices.

BFS shortest path (unweighted graph):

def bfs_shortest_path(graph: GraphList, start, end) -> list:
    """
    BFS finds shortest path from start to end (unweighted graph)
    Returns path as vertex list, or empty list if unreachable
    """
    if start == end:
        return [start]
    
    visited = {start}
    parent = {start: None}
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        for neighbor in graph.get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                if neighbor == end:
                    # Backtrack path
                    path = []
                    cur = end
                    while cur is not None:
                        path.append(cur)
                        cur = parent[cur]
                    return path[::-1]
                queue.append(neighbor)
    
    return []  # Unreachable

16.4 Depth-First Search (DFS)

DFS starts from a source vertex and explores as deep as possible along each branch before backtracking.

Core idea: Use a stack (implicit recursion stack or explicit stack). Always go deeper into an unvisited neighbor.

def dfs_recursive(graph: GraphList, start) -> list:
    """
    Depth-First Search — recursive version
    """
    visited = set()
    order = []
    
    def _dfs(node):
        visited.add(node)
        order.append(node)
        for neighbor in graph.get_neighbors(node):
            if neighbor not in visited:
                _dfs(neighbor)
    
    _dfs(start)
    return order


def dfs_iterative(graph: GraphList, start) -> list:
    """
    Depth-First Search — iterative version (explicit stack)
    """
    visited = set()
    order = []
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        
        # Push in reverse order to visit neighbors in original order
        for neighbor in reversed(graph.get_neighbors(node)):
            if neighbor not in visited:
                stack.append(neighbor)
    
    return order


# Example
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)

print(dfs_recursive(g, 0))  # [0, 1, 3, 2, 4] or another valid DFS order
print(dfs_iterative(g, 0))  # [0, 1, 3, 2, 4] or another valid DFS order

Key properties of DFS:

1. Depth-first: Explores as far as possible before backtracking.
2. Time complexity: O(V + E) — same as BFS.
3. Space complexity: O(V) — recursion stack depth can be V in the worst case (chain graph).
4. Versatile: Cycle detection, topological sort, connected components, bipartiteness testing.

BFS vs DFS comparison:

16.5 Connected Components

For an undirected graph that is not connected (not all vertices can reach each other), the graph consists of several connected components. Each connected component is a maximal connected subgraph.

def find_connected_components(graph: GraphList) -> list:
    """
    Find all connected components in an undirected graph
    Returns: list of lists, each sublist contains vertices of one component
    """
    visited = set()
    components = []
    
    for vertex in graph.vertices():
        if vertex not in visited:
            component = []
            queue = deque([vertex])
            visited.add(vertex)
            
            while queue:
                node = queue.popleft()
                component.append(node)
                for neighbor in graph.get_neighbors(node):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            
            components.append(component)
    
    return components


# Example: two disconnected subgraphs
g = GraphList()
g.add_edge(0, 1)
g.add_edge(1, 2)  # Component 1: {0, 1, 2}
g.add_edge(3, 4)  # Component 2: {3, 4}

print(find_connected_components(g))  # [[0, 1, 2], [3, 4]]

Core idea: Iterate over all vertices; for each unvisited vertex, launch BFS/DFS — all reachable vertices form one connected component.

Time complexity: O(V + E) — despite the outer loop, each vertex/edge is visited only once.

16.6 Bipartite Graph Testing

A bipartite graph is one whose vertices can be divided into two disjoint sets A and B such that every edge connects a vertex in A to one in B (no intra-set edges).

Testing method: Try to 2-color the graph. If adjacent vertices can always have different colors, the graph is bipartite; otherwise it is not.

def is_bipartite(graph: GraphList) -> bool:
    """
    Determine if an undirected graph is bipartite
    Uses BFS coloring
    """
    color = {}
    
    for start in graph.vertices():
        if start in color:
            continue
        
        queue = deque([start])
        color[start] = 0
        
        while queue:
            node = queue.popleft()
            for neighbor in graph.get_neighbors(node):
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    
    return True


# Example 1: bipartite (even cycle)
#   0 --- 1
#   |     |
#   3 --- 2
g1 = GraphList()
g1.add_edge(0, 1)
g1.add_edge(1, 2)
g1.add_edge(2, 3)
g1.add_edge(3, 0)
print(is_bipartite(g1))  # True

# Example 2: not bipartite (odd cycle — triangle)
g2 = GraphList()
g2.add_edge(0, 1)
g2.add_edge(1, 2)
g2.add_edge(2, 0)
print(is_bipartite(g2))  # False

Theorem: A graph is bipartite if and only if it contains no odd-length cycles (Konig, 1916).

Intuition: If there is an odd cycle, starting from any vertex and traversing the cycle leads to a color conflict upon return.

16.7 Common Mistakes

Mistake 1: Forgetting to mark visited

# Wrong: no visited set → infinite loop
def bfs_wrong(graph, start):
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph.get_neighbors(node):
            queue.append(neighbor)  # Infinite loop!

Mistake 2: DFS recursion depth exceeded

# Python default recursion limit is 1000
# For large graphs (e.g., 10000-node chain), recursive DFS will overflow
import sys
sys.setrecursionlimit(100000)  # Temporary fix
# Better: use iterative DFS

Mistake 3: Confusing connectivity in directed graphs

# In a directed graph, A→B does NOT mean B→A
# "A can reach B" ≠ "B can reach A"
# Undirected "connected" corresponds to "strongly connected" in directed graphs

Level 2 · How It Works Under the Hood

16.8 Storage Optimization: Sparse vs Dense

Let us quantitatively analyze the two representations under different graph densities.

Graph density is defined as: density d = |E| / (|V|² / 2) for undirected graphs, where |V|²/2 is the maximum possible number of edges. When d approaches 1, the graph is dense; when d approaches 0, it is sparse.

Real-world graph density comparison:

Memory comparison experiment:

import sys

def memory_comparison(V: int, E: int):
    """Compare memory usage of the two representations"""
    
    # Adjacency matrix: V×V integers
    # Each Python int ~28 bytes, but numpy can use 1 byte
    matrix_memory_numpy = V * V * 1   # numpy bool array
    
    # Adjacency list: each edge stored twice (undirected)
    adjlist_memory = E * 2 * 36  # Each list entry ~36 bytes
    
    print(f"Graph: V={V}, E={E}, density={2*E/(V*V):.6f}")
    print(f"Adjacency matrix (numpy): {matrix_memory_numpy / 1024 / 1024:.1f} MB")
    print(f"Adjacency list:           {adjlist_memory / 1024 / 1024:.1f} MB")
    print(f"Ratio: {matrix_memory_numpy / max(adjlist_memory, 1):.2f}")
    print()

# Sparse graph: 10000 nodes, 30000 edges
memory_comparison(10000, 30000)
# Matrix: 95.4 MB vs List: 2.1 MB → list wins

# Dense graph: 1000 nodes, 400000 edges
memory_comparison(1000, 400000)
# Matrix: 1.0 MB vs List: 27.5 MB → matrix wins

Engineering optimization strategies:

1. Compressed Sparse Row (CSR) format: For ultra-large sparse graphs. Uses three arrays:
   • values[]: all edge weights
   • col_indices[]: target vertex of each edge
   • row_offsets[]: starting position of each vertex's neighbors in col_indices

class GraphCSR:
    """Compressed Sparse Row — suitable for large read-only graphs"""
    
    def __init__(self, num_vertices, edges):
        """
        edges: List of (u, v, weight) tuples
        """
        self.n = num_vertices
        edges.sort(key=lambda e: e[0])
        
        self.col_indices = [e[1] for e in edges]
        self.weights = [e[2] for e in edges]
        
        self.row_offsets = [0] * (num_vertices + 1)
        for u, v, w in edges:
            self.row_offsets[u + 1] += 1
        for i in range(1, num_vertices + 1):
            self.row_offsets[i] += self.row_offsets[i - 1]
    
    def get_neighbors(self, u):
        """O(degree(u)) neighbor retrieval"""
        start = self.row_offsets[u]
        end = self.row_offsets[u + 1]
        return list(zip(self.col_indices[start:end], self.weights[start:end]))

2. Adjacency Set: If you need frequent edge-existence queries, replace the list with a set for amortized O(1) lookup:

class GraphSet:
    """Adjacency set: balances space efficiency and fast edge queries"""
    
    def __init__(self, directed=False):
        self.directed = directed
        self.adj = defaultdict(set)
    
    def add_edge(self, u, v):
        self.adj[u].add(v)
        if not self.directed:
            self.adj[v].add(u)
    
    def has_edge(self, u, v) -> bool:
        return v in self.adj[u]  # Average O(1)

16.9 BFS and Shortest Paths in Unweighted Graphs

The most important theoretical property of BFS is that it finds shortest paths in unweighted graphs. While intuitive, this requires rigorous proof.

Theorem: In an unweighted graph G = (V, E), when BFS starts from source s, for every vertex v, the number of edges BFS traverses to discover v equals the shortest path length from s to v.

Proof sketch:

Let δ(s,v) be the true shortest distance (minimum edges), and d(s,v) be the layer at which BFS discovers v.

1. d(s,v) ≥ δ(s,v): The path BFS takes to discover v is a valid path, which cannot be shorter than the shortest path.
2. d(s,v) ≤ δ(s,v): By induction. Assume the claim holds for all vertices at distance < k. For a vertex v with δ(s,v) = k, there exists a neighbor u with δ(s,u) = k-1. By the inductive hypothesis, BFS discovers u at layer k-1, then when processing u's neighbors it discovers v (if not yet discovered), placing v at layer k.

Therefore d(s,v) = δ(s,v). □

Complete BFS with level information:

def bfs_with_levels(graph: GraphList, start):
    """
    BFS recording distance and parent for each node
    Returns (distance, parent) dictionaries
    """
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        for neighbor in graph.get_neighbors(node):
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                parent[neighbor] = node
                queue.append(neighbor)
    
    return dist, parent


def reconstruct_path(parent: dict, start, end) -> list:
    """Reconstruct shortest path from parent dictionary"""
    if end not in parent:
        return []
    path = []
    cur = end
    while cur is not None:
        path.append(cur)
        cur = parent[cur]
    return path[::-1]


# Example: Six Degrees of Separation
g = GraphList()
edges = [(0,1),(0,2),(1,3),(2,4),(3,5),(4,5),(5,6)]
for u, v in edges:
    g.add_edge(u, v)

dist, parent = bfs_with_levels(g, 0)
print(f"Shortest distance from 0 to 6: {dist[6]}")  # 3
print(f"Shortest path: {reconstruct_path(parent, 0, 6)}")  # [0, 1, 3, 5, 6]

Multi-source BFS:

Sometimes you need to BFS from multiple sources simultaneously. For example, "find the distance from each empty cell to the nearest building." The trick is to enqueue all sources at the start:

def multi_source_bfs(graph: GraphList, sources: list) -> dict:
    """
    Multi-source BFS: start from multiple sources simultaneously
    Returns distance from each vertex to the nearest source
    """
    dist = {}
    queue = deque()
    
    for s in sources:
        dist[s] = 0
        queue.append(s)
    
    while queue:
        node = queue.popleft()
        for neighbor in graph.get_neighbors(node):
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    
    return dist

16.10 DFS Timestamps and Edge Classification

DFS has an extremely powerful tool: timestamps. During DFS, we record two times for each vertex:

• Discovery time d[v]: the moment v is first visited
• Finish time f[v]: the moment all descendants of v have been fully explored

class DFSWithTimestamp:
    """DFS with timestamps"""
    
    def __init__(self, graph: GraphList):
        self.graph = graph
        self.discovery = {}
        self.finish = {}
        self.parent = {}
        self.time = 0
        self.edge_type = {}
    
    def dfs(self):
        """Run DFS on entire graph"""
        for v in self.graph.vertices():
            self.parent[v] = None
        
        for v in self.graph.vertices():
            if v not in self.discovery:
                self._dfs_visit(v)
    
    def _dfs_visit(self, u):
        """Visit vertex u"""
        self.time += 1
        self.discovery[u] = self.time
        
        for v in self.graph.get_neighbors(u):
            if v not in self.discovery:
                # v undiscovered → tree edge
                self.edge_type[(u, v)] = "tree"
                self.parent[v] = u
                self._dfs_visit(v)
            elif v not in self.finish:
                # v discovered but not finished → back edge (cycle detected!)
                self.edge_type[(u, v)] = "back"
            elif self.discovery[u] < self.discovery[v]:
                # v finished, discovered after u → forward edge
                self.edge_type[(u, v)] = "forward"
            else:
                # v finished, discovered before u → cross edge
                self.edge_type[(u, v)] = "cross"
        
        self.time += 1
        self.finish[u] = self.time


# Example: directed graph
g = GraphList(directed=True)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(3, 0)  # Back edge: forms cycle 0→1→3→0
g.add_edge(2, 3)

dfs = DFSWithTimestamp(g)
dfs.dfs()

print("Discovery/Finish times:")
for v in sorted(dfs.discovery.keys()):
    print(f"  Vertex {v}: d={dfs.discovery[v]}, f={dfs.finish[v]}")

print("\nEdge classification:")
for edge, etype in dfs.edge_type.items():
    print(f"  {edge[0]} → {edge[1]}: {etype}")

The four edge types:

Parenthesis Theorem:

For any two vertices u and v, exactly one of these holds:

1. Intervals [d[u], f[u]] and [d[v], f[v]] are completely disjoint → u and v have no ancestor-descendant relationship in the DFS tree
2. [d[u], f[u]] completely contains [d[v], f[v]] → v is a descendant of u
3. [d[v], f[v]] completely contains [d[u], f[u]] → u is a descendant of v

This is like nested parentheses — discovery is an "opening bracket," finish is a "closing bracket." Brackets either nest or are disjoint; they never partially overlap.

White Path Theorem:

In a DFS, v is a descendant of u if and only if at the time u is discovered, there exists a path from u to v consisting entirely of white (undiscovered) vertices.

These two theorems form the theoretical foundation for DFS applications (topological sort, strongly connected components, articulation points/bridges).

16.11 Cycle Detection Using DFS

Undirected graph cycle detection:

In an undirected graph, if DFS encounters a visited vertex that is not the current node's parent, a cycle exists.

def has_cycle_undirected(graph: GraphList) -> bool:
    """Undirected graph cycle detection"""
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph.get_neighbors(node):
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
    
    for v in graph.vertices():
        if v not in visited:
            if dfs(v, -1):
                return True
    return False

Directed graph cycle detection:

In a directed graph, a cycle exists if and only if DFS discovers a back edge.

def has_cycle_directed(graph: GraphList) -> bool:
    """Directed graph cycle detection: three-color method"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph.vertices()}
    
    def dfs(node):
        color[node] = GRAY
        for neighbor in graph.get_neighbors(node):
            if color[neighbor] == GRAY:
                return True  # Back edge → cycle
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True
        color[node] = BLACK
        return False
    
    for v in graph.vertices():
        if color[v] == WHITE:
            if dfs(v):
                return True
    return False

Three-color intuition:

• White: not yet explored
• Gray: currently being explored (on the current DFS path)
• Black: fully explored

If from a gray node we reach another gray node, we have found a path from that gray node back to itself — a cycle.

16.12 Graph Traversal Application Patterns

Pattern 1: Grid Graph

Many interview problems treat a 2D grid as a graph where each cell is a vertex and adjacent cells (up/down/left/right) share edges.

def grid_bfs(grid: list, start_row: int, start_col: int):
    """BFS on a 2D grid"""
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    visited = set()
    visited.add((start_row, start_col))
    queue = deque([(start_row, start_col, 0)])
    
    while queue:
        r, c, dist = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and 
                (nr, nc) not in visited and grid[nr][nc] != '#'):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

Pattern 2: Implicit Graph

Some problems define a graph implicitly through states and transition rules. For example, "starting from number x, you can +1, ×2, or -1 each step — what is the minimum number of steps to reach y?" This is BFS on an implicit graph.

def min_operations(start: int, target: int) -> int:
    """From start to target, each step can be +1, -1, or ×2"""
    if start >= target:
        return start - target
    
    visited = set([start])
    queue = deque([(start, 0)])
    
    while queue:
        num, steps = queue.popleft()
        for next_num in [num + 1, num - 1, num * 2]:
            if next_num == target:
                return steps + 1
            if 0 <= next_num <= 2 * target and next_num not in visited:
                visited.add(next_num)
                queue.append((next_num, steps + 1))
    
    return -1

Level 3 · How the Specification Defines It

16.13 Euler and the Birth of Graph Theory: The Seven Bridges Problem (1736)

The birth of graph theory as a mathematical discipline can be traced to a precise moment: in 1736, Swiss mathematician Leonhard Euler published the paper "Solutio problematis ad geometriam situs pertinentis" (Solution of a problem relating to the geometry of position), solving the famous Konigsberg Bridge Problem.

Historical context: 18th-century Konigsberg (now Kaliningrad, Russia) had a river (the Pregel) running through the city with two islands. The city's four landmasses were connected by seven bridges. Citizens asked: can one find a route that crosses each bridge exactly once and returns to the starting point?

Abstract graph of the Seven Bridges:

The four landmasses (A, B, C, D) as vertices:
  A has degree 5 (connected to B×2, C×2, D×1)
  B has degree 3 (connected to A×2, D×1)
  C has degree 3 (connected to A×2, D×1)
  D has degree 3 (connected to A×1, B×1, C×1)

Euler's solution:

Euler made a brilliant abstraction — he ignored the areas of landmasses, lengths of bridges, and shapes of routes, focusing only on connectivity. He abstracted the four landmasses as vertices and the seven bridges as edges, transforming a geographic problem into a purely mathematical one.

This abstraction itself is the birth moment of graph theory.

Euler's Theorem: A connected graph has an Eulerian circuit (traverses every edge exactly once and returns to the start) if and only if every vertex has even degree. It has an Eulerian path (traverses every edge exactly once without necessarily returning) if and only if it has exactly 0 or 2 vertices of odd degree.

Proof (necessity): If an Eulerian circuit exists, then each time the path passes through a vertex, it must "enter via one edge and leave via another" — consuming two edges. For non-starting vertices, all edges are consumed in pairs, so degree must be even. The starting vertex initially "leaves" on one edge and finally "returns" on one edge, with the rest also paired, so its degree is also even.

Applied to the Seven Bridges: The four vertices have degrees 5, 3, 3, 3 — all odd! Therefore no Eulerian circuit exists, and no Eulerian path exists either (4 odd-degree vertices, not 0 or 2).

def has_eulerian_circuit(graph: GraphList) -> bool:
    """Check if a connected undirected graph has an Eulerian circuit"""
    for v in graph.vertices():
        if graph.degree(v) % 2 != 0:
            return False
    return True

def has_eulerian_path(graph: GraphList) -> tuple:
    """
    Check if a connected undirected graph has an Eulerian path
    Returns (exists, start_vertex)
    """
    odd_degree_vertices = [v for v in graph.vertices() if graph.degree(v) % 2 != 0]
    
    if len(odd_degree_vertices) == 0:
        return True, next(iter(graph.vertices()))
    elif len(odd_degree_vertices) == 2:
        return True, odd_degree_vertices[0]
    else:
        return False, None

Historical significance:

Euler's contribution went beyond solving the bridge problem:

1. Founded graph theory: Abstracting concrete problems into "vertices + edges" mathematical structures
2. Pioneered topological thinking: Caring only about connectivity, not metrics (distances, areas)
3. Proved impossibility: Not finding an answer, but proving no answer exists — a profoundly important mode of mathematical reasoning

16.14 Graph Representation in Social Networks and Recommendation Systems

The core products of the modern internet — social networks and recommendation systems — are essentially engineering implementations of large-scale graph algorithms.

Social Networks: Facebook's TAO

Facebook's (Meta's) social graph has approximately 3 billion vertices and hundreds of billions of edges. Their graph storage system TAO (The Associations and Objects) was published by Bronson et al. at USENIX ATC 2013.

TAO's core design decisions:

1. Separate objects and associations: Vertices (users, posts, comments) stored as Objects; edges (friendships, likes, comments) stored as Associations.
2. Adjacency list sharding: Sharded by source vertex ID hash; each shard stores a subset of adjacency lists.
3. Reverse edge index: For queries like "who follows me," maintain reverse adjacency lists.
4. Tiered caching: Hot vertices (celebrities) have adjacency lists cached in memory.

class SocialGraph:
    """Simplified model of social network graph storage"""
    
    def __init__(self):
        self.forward = defaultdict(set)
        self.reverse = defaultdict(set)
    
    def add_follow(self, follower: int, followee: int, timestamp: int):
        """A follows B"""
        self.forward[follower].add((followee, timestamp, "follow"))
        self.reverse[followee].add((follower, timestamp))
    
    def get_following(self, user: int) -> list:
        """Get list of people a user follows"""
        return [(uid, ts) for uid, ts, _ in self.forward[user]]
    
    def get_followers(self, user: int) -> list:
        """Get follower list"""
        return list(self.reverse[user])
    
    def mutual_friends(self, u: int, v: int) -> set:
        """Mutual friends — neighbor set intersection"""
        friends_u = {uid for uid, _, _ in self.forward[u]}
        friends_v = {uid for uid, _, _ in self.forward[v]}
        return friends_u & friends_v

Recommendation Systems: Graph-Based Collaborative Filtering

A classic approach in recommendation systems is to model users and items as a bipartite graph, then leverage graph structure for recommendations.

Idea: If users A and B share many liked items (many length-2 paths in the bipartite graph), then items A likes but B hasn't seen can be recommended to B.

def recommend_items(user_item_graph: dict, target_user: int, top_k: int = 5) -> list:
    """
    Simple bipartite-graph-based recommendation
    user_item_graph: {user_id: set of item_ids}
    """
    target_items = user_item_graph[target_user]
    item_scores = defaultdict(float)
    
    for other_user, other_items in user_item_graph.items():
        if other_user == target_user:
            continue
        
        common = target_items & other_items
        if not common:
            continue
        similarity = len(common) / len(target_items | other_items)
        
        for item in other_items - target_items:
            item_scores[item] += similarity
    
    recommended = sorted(item_scores.items(), key=lambda x: -x[1])
    return [item for item, score in recommended[:top_k]]

Google's PageRank: Generalization of BFS Thinking

Larry Page and Sergey Brin's PageRank algorithm (1998) is essentially a random walk on a directed graph (the web link graph). It can be viewed as a probabilistic version of BFS:

• BFS: from a source, deterministically visit all reachable vertices
• PageRank: from any vertex, randomly follow edges; the eventual "visit frequency" of each vertex is its importance

def pagerank(graph: GraphList, damping: float = 0.85, iterations: int = 100):
    """
    Simplified PageRank algorithm
    damping: probability of following a link (vs random jump)
    """
    vertices = list(graph.vertices())
    n = len(vertices)
    rank = {v: 1.0 / n for v in vertices}
    
    for _ in range(iterations):
        new_rank = {v: (1 - damping) / n for v in vertices}
        
        for u in vertices:
            neighbors = graph.get_neighbors(u)
            if neighbors:
                share = damping * rank[u] / len(neighbors)
                for v in neighbors:
                    new_rank[v] += share
        
        rank = new_rank
    
    return rank

16.15 Formal Graph Traversal: Definitions from Cormen et al. (CLRS)

Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein, 3rd edition 2009), Chapter 22, provides the standard formalization of BFS and DFS.

BFS Invariant:

At any point during BFS, vertices in the queue are ordered by distance: if u was enqueued before v, then d[u] ≤ d[v], and adjacent elements in the queue differ in distance by at most 1.

Formally: let the queue be ⟨v₁, v₂, ..., vₖ⟩. Then d[vₖ] ≤ d[v₁] + 1, and d[vᵢ] ≤ d[vᵢ₊₁].

This guarantees BFS's "layer by layer" expansion behavior.

DFS Structural Theorems:

CLRS proves that DFS timestamps satisfy:

1. Parenthesis Theorem (as described in Section 16.10)
2. Descendant Theorem: In the DFS forest, v is a descendant of u ⟺ d[u] < d[v] < f[v] < f[u]
3. Back Edge Theorem: Directed graph G has a cycle ⟺ DFS of G produces a back edge

These theorems elevate DFS from "a search algorithm" to "a general-purpose tool for analyzing graph structure."

Level 4 · Edge Cases and Pitfalls

16.16 LeetCode 200: Number of Islands

Problem: Given an m×n 2D grid where '1' represents land and '0' represents water, count the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically.

Analysis: This is essentially counting connected components of '1' cells in a grid graph.

from collections import deque

def numIslands(grid: list) -> int:
    """
    LeetCode 200: Number of Islands
    Time O(m×n), Space O(m×n)
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def bfs(r, c):
        """BFS from (r,c) to mark entire island"""
        queue = deque([(r, c)])
        grid[r][c] = '0'
        
        while queue:
            row, col = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols 
                    and grid[nr][nc] == '1'):
                    grid[nr][nc] = '0'
                    queue.append((nr, nc))
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                bfs(i, j)
    
    return count


# DFS version (more concise, but may stack overflow on large grids)
def numIslands_dfs(grid: list) -> int:
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count


# Test
grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
]
print(numIslands([row[:] for row in grid]))  # 3

Interview tips:

• Time complexity O(m×n): each cell visited at most once
• Space complexity O(m×n): worst case the entire grid is one island
• Modifying grid directly as visited marker avoids extra space (but mutates input)
• If input cannot be modified, use a separate visited set

16.17 LeetCode 133: Clone Graph

Problem: Given a reference to a node in a connected undirected graph, return a deep copy. Each node has an integer value and a list of neighbors.

Analysis: Graph traversal + hash map. BFS or DFS through the original graph, creating a clone for each node, using a dictionary to map "original → clone."

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: 'Node') -> 'Node':
    """
    LeetCode 133: Clone Graph
    BFS + HashMap
    Time O(V+E), Space O(V)
    """
    if not node:
        return None
    
    cloned = {node: Node(node.val)}
    queue = deque([node])
    
    while queue:
        current = queue.popleft()
        
        for neighbor in current.neighbors:
            if neighbor not in cloned:
                cloned[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            cloned[current].neighbors.append(cloned[neighbor])
    
    return cloned[node]


# DFS version
def cloneGraph_dfs(node: 'Node') -> 'Node':
    if not node:
        return None
    
    cloned = {}
    
    def dfs(n):
        if n in cloned:
            return cloned[n]
        clone = Node(n.val)
        cloned[n] = clone
        for neighbor in n.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone
    
    return dfs(node)

Interview tips:

• The HashMap is crucial to avoid duplicate cloning and infinite loops
• Master both BFS and DFS approaches
• Time O(V+E), Space O(V)

16.18 LeetCode 207: Course Schedule

Problem: There are n courses (0 to n-1). prerequisites[i] = [a, b] means you must take b before a. Determine if it is possible to finish all courses (i.e., does the directed graph have a cycle?).

Analysis: Model courses as directed graph vertices, prerequisites as edges. The problem reduces to detecting whether the directed graph has a cycle (a cycle means some courses are impossible to complete).

def canFinish(numCourses: int, prerequisites: list) -> bool:
    """
    LeetCode 207: Course Schedule
    Directed graph cycle detection — DFS three-color method
    Time O(V+E), Space O(V+E)
    """
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)
    
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * numCourses
    
    def has_cycle(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE:
                if has_cycle(neighbor):
                    return True
        color[node] = BLACK
        return False
    
    for i in range(numCourses):
        if color[i] == WHITE:
            if has_cycle(i):
                return False
    
    return True


# BFS version (Kahn's algorithm — topological sort)
def canFinish_bfs(numCourses: int, prerequisites: list) -> bool:
    """BFS topological sort: if all nodes can be sorted, no cycle exists"""
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0
    
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return count == numCourses


# Test
print(canFinish(2, [[1,0]]))          # True
print(canFinish(2, [[1,0],[0,1]]))    # False (cycle)
print(canFinish(4, [[1,0],[2,1],[3,2]]))  # True

16.19 LeetCode 130: Surrounded Regions

Problem: Given an m×n matrix containing 'X' and 'O', capture all regions surrounded by 'X'. A region is surrounded if it is not connected to any 'O' on the border.

Analysis: Reverse thinking! Instead of finding "surrounded O's," find "unsurrounded O's" (reachable from the border), then flip all remaining O's.

def solve(board: list) -> None:
    """
    LeetCode 130: Surrounded Regions
    BFS from border, mark unsurrounded 'O's
    Time O(m×n), Space O(m×n)
    """
    if not board or not board[0]:
        return
    
    rows, cols = len(board), len(board[0])
    
    def bfs(r, c):
        """Mark all 'O's connected to border as 'S' (safe)"""
        queue = deque([(r, c)])
        board[r][c] = 'S'
        while queue:
            row, col = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols 
                    and board[nr][nc] == 'O'):
                    board[nr][nc] = 'S'
                    queue.append((nr, nc))
    
    # Step 1: Mark all safe 'O's starting from borders
    for i in range(rows):
        if board[i][0] == 'O':
            bfs(i, 0)
        if board[i][cols-1] == 'O':
            bfs(i, cols-1)
    for j in range(cols):
        if board[0][j] == 'O':
            bfs(0, j)
        if board[rows-1][j] == 'O':
            bfs(rows-1, j)
    
    # Step 2: Flip remaining 'O' to 'X', restore 'S' to 'O'
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'S':
                board[i][j] = 'O'


# Test
board = [
    ['X','X','X','X'],
    ['X','O','O','X'],
    ['X','X','O','X'],
    ['X','O','X','X']
]
solve(board)
for row in board:
    print(row)
# ['X','X','X','X']
# ['X','X','X','X']
# ['X','X','X','X']
# ['X','O','X','X']  ← bottom-left O connected to border, not flipped

Interview tips:

• Reverse thinking is the key insight: start from the border to find safe regions
• Three-step approach: mark safe → flip unsafe O → restore safe
• Time O(m×n), Space O(m×n) (BFS queue)

16.20 Universal Framework for Graph Interview Problems

Graph problems in interviews are highly varied, but the underlying approach follows a common framework:

Step 1: Recognize "this is a graph problem"

Signal words: connected, adjacent, reachable, shortest path, dependency, grid, matrix traversal.

Step 2: Model the problem

• What are the vertices? What are the edges?
• Directed or undirected? Weighted or unweighted?
• Explicit graph (adjacency given) or implicit graph (derive neighbors from rules)?

Step 3: Choose the algorithm

Step 4: Consider edge cases

• Empty graph (0 vertices)
• Disconnected graph (multiple components)
• Self-loops
• Parallel edges

16.21 Chapter Summary

Graphs are the most versatile data structure in computer science — virtually any relationship can be modeled as a graph. Mastering graph representation and traversal gives you the foundational tool for solving a vast range of real problems. In the next chapter, we will explore a key application of directed graphs: topological sorting.