Graphs

Graph vocabulary

A graph G = (V, E) is a set of vertices (nodes) V and a set of edges E, each connecting two vertices. We write n = |V| and m = |E|; graph algorithm costs are stated in both.

A tree is a connected, acyclic, undirected graph; it always has exactly n − 1 edges. Everything from M24 is a special case of what follows.

Representations and their trade-offs

Breadth-first search and shortest paths

BFS explores in rings: the start vertex, then everything one edge away, then everything two edges away. A FIFO queue makes this happen, because vertices discovered earlier are processed earlier. Mark a vertex as visited when you enqueue it (not when you dequeue it), or the same vertex can be queued many times.

The key property: the first time BFS reaches a vertex, it has found a path with the fewest edges. So BFS solves shortest paths in unweighted graphs. Record each vertex's parent (the vertex it was discovered from) and you can rebuild the path by walking parents back from the target. Each vertex is enqueued once and each edge examined at most twice, so BFS costs O(n + m).

Depth-first search: recursive and iterative

DFS goes as deep as it can along one path, then backtracks. It is the graph version of pre-order tree traversal, with a visited set to avoid going around cycles forever. DFS does not find shortest paths, but its structure (when each vertex is entered and finished) is what cycle detection, topological sorting, and many other algorithms build on. Also O(n + m).

Notice the iterative version marks a vertex visited when it is popped, unlike BFS. That is what makes its order match the recursive one. It also means a vertex can sit on the stack several times; the continue skips the duplicates.

Connected components, cycles, and bipartite graphs

Connected components

Run a traversal from every vertex not yet visited; each run discovers exactly one component. Total cost is still O(n + m) because every vertex and edge is processed once across all runs. Uses: clustering, finding isolated groups in a network, checking whether a road network is fully connected.

Cycle detection

In an undirected graph, a cycle exists if DFS meets an already-visited vertex that is not the vertex it just came from (its parent). In a directed graph that test is wrong: reaching a finished vertex through a different route is fine (a diamond A→B→D, A→C→D has no cycle). Instead use three colors: white (unvisited), gray (on the current DFS path), black (finished). An edge into a gray vertex is a back edge, and a back edge means a cycle.

Bipartite check

A graph is bipartite if its vertices split into two groups with every edge going between the groups: students and courses, job applicants and jobs, or "can these meetings be split across two rooms so no conflicting pair shares one?" Test it by BFS 2-coloring: color the start 0, its neighbors 1, their neighbors 0, and so on. A conflict (an edge between same colors) means an odd cycle, and the graph is not bipartite.

Topological sort

A topological order of a DAG lists every vertex before all the vertices it points to. If edges mean "must come before" (u → v: do u before v), it is a valid schedule. Build systems, package installers, spreadsheet recalculation, and course planners all need one. A topological order exists if and only if the graph has no directed cycle, and there are usually many valid orders.

The standard library has this built in. graphlib.TopologicalSorter takes a mapping from each node to its predecessors (the things it depends on, which is the opposite direction from the dict above), raises graphlib.CycleError on cycles, and supports parallel scheduling: get_ready() returns every node whose dependencies are done, so independent tasks can run at the same time.

Grids as implicit graphs

Many problems hide a graph without ever building one. In a grid (a maze, an image, a game board), each cell is a vertex and its up/down/left/right neighbors are its edges. You compute neighbors on the fly instead of storing an adjacency list: an implicit graph. BFS on a maze finds the shortest route; DFS or BFS from a pixel is the paint-bucket flood fill; counting how many traversals you start is the number of islands.

Graphs in the real world

Pitfalls

• Marking visited too late in BFS. Mark on enqueue; marking on dequeue lets a vertex enter the queue once per incoming edge.
• Forgetting disconnected parts. A single traversal only sees one component. Loop over all vertices.
• Using the undirected cycle test on a directed graph. A diamond has no cycle; use three colors.
• Edge direction confusion. "a depends on b" and "b before a" are opposite arrows. graphlib wants predecessors; Kahn's algorithm as written above wants successors. Write the convention in a comment.
• Deep recursion. Recursive DFS on a long chain or large grid raises RecursionError.
• Iterating a set gives arbitrary order. Algorithms are still correct, but output is not reproducible across runs with string hashing. Sort neighbors when determinism matters (tests, teaching).
• Adjacency matrices for sparse graphs. A million-vertex road network would need 10¹² cells.

Practice

def build_graph(vertices, edges, directed=False):
    graph = {v: set() for v in vertices}
    for u, v in edges:
        graph[u].add(v)
        if not directed:
            graph[v].add(u)
    return graph

def degrees(graph):
    return {v: len(ns) for v, ns in graph.items()}

from collections import deque

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        if u == goal:
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1]
        for v in graph[u]:
            if v not in parent:
                parent[v] = u
                queue.append(v)
    return None

def count_components(graph):
    seen, count = set(), 0
    for s in graph:
        if s in seen:
            continue
        count += 1
        seen.add(s)
        stack = [s]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
    return count

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph}

    def visit(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return True
            if color[v] == WHITE and visit(v):
                return True
        color[u] = BLACK
        return False

    return any(color[v] == WHITE and visit(v) for v in graph)

import heapq

def topo_sort(deps):
    nodes = set(deps)
    for ds in deps.values():
        nodes |= set(ds)
    indegree = {n: 0 for n in nodes}
    successors = {n: [] for n in nodes}
    for task, ds in deps.items():
        for d in ds:
            successors[d].append(task)
            indegree[task] += 1
    ready = [n for n in nodes if indegree[n] == 0]
    heapq.heapify(ready)
    order = []
    while ready:
        n = heapq.heappop(ready)
        order.append(n)
        for s in successors[n]:
            indegree[s] -= 1
            if indegree[s] == 0:
                heapq.heappush(ready, s)
    if len(order) != len(nodes):
        raise ValueError("dependency cycle")
    return order

from collections import deque

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen, count = set(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or (r, c) in seen:
                continue
            count += 1
            seen.add((r, c))
            queue = deque([(r, c)])
            while queue:
                cr, cc = queue.popleft()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and (nr, nc) not in seen:
                        seen.add((nr, nc))
                        queue.append((nr, nc))
    return count

Mini-project: a course-prerequisite planner

pixi init planner && cd planner
pixi add python=3.14 pytest
pixi run python planner.py catalog.toml --max-per-term 3

[courses]
"CS101" = []
"CS102" = ["CS101"]
"MATH120" = []
"CS201" = ["CS102", "MATH120"]
"CS250" = ["CS201"]

Quiz

Recap

• A graph is vertices plus edges, directed or not, weighted or not. Trees are connected acyclic graphs.
• Use adjacency lists (dict[str, set[str]]) by default; matrices only for small dense graphs.
• BFS (queue, mark on enqueue) gives fewest-edge paths; DFS (stack or recursion) gives the structure that cycle detection and topological sort need. Both are O(n + m).
• Components: start a traversal from each unvisited vertex. Directed cycles: three colors. Bipartite: BFS two-coloring.
• Topological sort: Kahn's in-degree queue, reversed DFS finish order, or graphlib.TopologicalSorter (node → predecessors).
• Grids are implicit graphs; compute neighbors on the fly and prefer iteration over recursion.

Going further

• graphlib: functionality to operate with graph-like structures
• collections.deque
• NetworkX documentation
• Next: M27 Advanced Structures (union-find gives another way to track components), then weighted paths in M31 Graph Algorithms.