Chapter 8: Graphs

Vol 2: Algorithm Forest Adventure · Station 8

---

Metadata Card

Attribute	Value
Difficulty	(Most versatile)
Prerequisites	Arrays, Linked Lists, Stacks & Queues, Recursion
Keywords	Adjacency Matrix Adjacency List DFS BFS Topological Sort Connected Components Bipartite Graph

---

Your Progress

The paths are no longer simple tree branches. Before you is a massive network — every location (node) connects to many others. Graphs are the most general map form you'll encounter in the forest.

---

Breakthrough · Origins

Two Storage Schemes

# Adjacency Matrix
class GraphMatrix:
    def __init__(self, n):
        self.adj = [[0] * n for _ in range(n)]
        self.n = n

    def add_edge(self, u, v, directed=False):
        self.adj[u][v] = 1
        if not directed:
            self.adj[v][u] = 1

    def has_edge(self, u, v):
        return self.adj[u][v] == 1

# Adjacency List
class GraphList:
    def __init__(self, n):
        self.adj = [[] for _ in range(n)]
        self.n = n

    def add_edge(self, u, v, directed=False):
        self.adj[u].append(v)
        if not directed:
            self.adj[v].append(u)

Criterion	Adj. Matrix	Adj. List
Space	O(V²)	O(V + E)
has_edge(u, v)	O(1)	O(degree)
Iterate neighbors	O(V)	O(degree)
Best for	Dense graphs (E ~ V²)	Sparse graphs (most real-world)

DFS (Depth-First Search)

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(f"visiting {start}", end=" → ")
    for neighbor in graph.adj[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(f"visiting {node}", end=" → ")
            for neighbor in reversed(graph.adj[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

BFS (Breadth-First Search)

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(f"visiting {node}", end=" → ")
        for neighbor in graph.adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

Topological Sort (Kahn's Algorithm)

def topological_sort_kahn(graph):
    n = graph.n
    in_degree = [0] * n
    for u in range(n):
        for v in graph.adj[u]:
            in_degree[v] += 1
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph.adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    if len(result) != n:
        raise ValueError("Graph contains a cycle")
    return result

Bipartite Graph Detection

def is_bipartite(graph):
    color = [-1] * graph.n
    for start in range(graph.n):
        if color[start] == -1:
            color[start] = 0
            q = deque([start])
            while q:
                u = q.popleft()
                for v in graph.adj[u]:
                    if color[v] == -1:
                        color[v] = 1 - color[u]
                        q.append(v)
                    elif color[v] == color[u]:
                        return False
    return True

---

Verification Checklist

• [ ] Can explain when to use adjacency matrix vs list
• [ ] Can hand-write DFS and BFS (recursive + iterative)
• [ ] Can implement topological sort (Kahn algorithm)
• [ ] Can detect bipartite graphs using BFS coloring

---

Traveler's Notes

1. DFS = Stack = go deep then backtrack. Good for reachability, connectivity.
2. BFS = Queue = expand layer by layer. Good for shortest path (unweighted).
3. Topological sort = dependency resolution (DAG only).
4. Bipartite = 2-coloring problem.

---

→ Next Stop Preview

Chapter 9: Sorting Algorithms (Part 1) — "From O(n²) to O(n log n)."