17. Graph Theory

Level: Intermediate You'll use this for: network topology, routing, dependency graphs, social graphs, and attack-path modeling.

Representations

# Adjacency list — efficient for sparse graphs (most real networks)
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

# Adjacency matrix — efficient for dense graphs, enables linear-algebra tricks (Ch. 11)
import numpy as np
nodes = ["A", "B", "C", "D"]
M = np.array([
    [0,1,1,0],
    [1,0,0,1],
    [1,0,0,1],
    [0,1,1,0],
])

Traversal: BFS vs. DFS

• BFS (breadth-first search): explores level by level — finds the shortest path (in unweighted graphs) and is used for "closest nodes first" problems.
• DFS (depth-first search): explores as deep as possible before backtracking — used for cycle detection, topological sort, and exhaustive path enumeration.

from collections import deque

def bfs_shortest_path(graph, start, goal):
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])
    return None

print(bfs_shortest_path(graph, "A", "D"))   # ['A', 'B', 'D'] or ['A', 'C', 'D']

Dijkstra's algorithm — shortest path with weighted edges

Used by every link-state routing protocol (OSPF, IS-IS) to compute the shortest path tree from a router to every other router in the network.

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

weighted_graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("A", 1), ("C", 2), ("D", 5)],
    "C": [("A", 4), ("B", 2), ("D", 1)],
    "D": [("B", 5), ("C", 1)],
}
print(dijkstra(weighted_graph, "A"))   # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Tracing Dijkstra by hand on that same graph, starting from A. Keep a running "best known distance" per node, always expanding the closest unvisited node next:

Start: distances = {A:0, B:∞, C:∞, D:∞}

Visit A (dist 0), its edges: B (1), C (4)
  -> B: 0+1=1 < ∞, update B to 1
  -> C: 0+4=4 < ∞, update C to 4
  distances = {A:0, B:1, C:4, D:∞}

Visit B (dist 1, the smallest unvisited), its edges: A (1), C (2), D (5)
  -> A: already visited, skip
  -> C: 1+2=3 < 4, update C to 3   <- found a shorter path to C via B!
  -> D: 1+5=6 < ∞, update D to 6
  distances = {A:0, B:1, C:3, D:6}

Visit C (dist 3, now the smallest unvisited), its edges: A (4), B (2), D (1)
  -> D: 3+1=4 < 6, update D to 4   <- found a shorter path to D via C!
  distances = {A:0, B:1, C:3, D:4}

Visit D (dist 4) — no shorter paths found through it. Done.

Final: A=0, B=1, C=3, D=4   ✓ matches the code output

The key move is that C's distance got revised twice (4, then 3) — Dijkstra never commits to a distance as final until that node is actually visited, which is exactly why it always finds the true shortest path instead of just the first path found.

Bellman-Ford is the alternative used when edge weights can be negative (Dijkstra breaks with negative weights) — this is why distance-vector protocols like the classic RIP use a Bellman-Ford variant, while OSPF (Dijkstra-based) requires non-negative link costs.

Why Dijkstra is correct (and why negative weights break it)

Invariant: when a node is taken off the priority queue, its distance is final.

Proof sketch. Suppose node u is popped with distance d(u), but some shorter path to u exists. That path starts inside the set of already-final nodes and must leave it at some edge into a not-yet-final node y. Every edge weight is non-negative, so the path's length is at least d(y). And d(y) ≥ d(u), because the queue popped u first, not y. So the "shorter" path is no shorter, a contradiction. ∎

The proof uses non-negativity exactly once ("the rest of the path can't make it shorter"). A negative edge breaks that step, which is why Dijkstra fails on negative weights.

Cost: with a binary heap, O((V + E) · log V). OSPF recomputes this after every topology change. For a 1,000-router area with about 5,000 links that's around 60,000 heap operations, a few milliseconds. The expensive part of convergence is flooding the link-state updates, not the maths.

Bellman–Ford and count-to-infinity

Distance-vector routing runs the Bellman–Ford update distributed. Each router repeatedly applies:

d(x) = min over neighbours v of [ cost(x, v) + d_v(destination) ]

It converges in at most V - 1 rounds when costs are stable. But when a link fails, bad news travels slowly. Take a chain A – B – C, where C is the destination. If the B–C link dies, B hears A advertise "C is 2 hops away". That route actually goes back through B, but B doesn't know that. So B sets its distance to 3, A updates to 4, B to 5, and so on, one hop per exchange. This is count to infinity. RIP caps "infinity" at 16 hops, so a destination is declared unreachable after about 16 exchanges, which is the reason RIP networks can't be wider than 15 hops. Split horizon and poison reverse suppress the simple case. Path-vector protocols (BGP) carry the whole path, so a router can see its own name in a route and reject the loop.

Max-flow / min-cut: how much can this network carry?

Each link has a capacity. What's the maximum rate from source S to sink T?

      ┌──10──▶ A ──4───┐
      │        │       ▼
      S       15       T
      │        ▼       ▲
      └──5───▶ B ──10──┘

Links: S→A 10, S→B 5, A→B 15, A→T 4, B→T 10.

Theorem (Max-flow min-cut, Ford & Fulkerson, 1956). The maximum flow from S to T equals the minimum total capacity of any cut, a set of links whose removal disconnects T from S.

Finding the flow by hand (augmenting paths):

path S→A→T:     bottleneck min(10, 4)      = 4     A→T now full
path S→B→T:     bottleneck min(5, 10)      = 5     S→B now full
path S→A→B→T:   bottleneck min(10-4, 15, 10-5) = 5  B→T now full
no more paths with spare capacity.          total = 4 + 5 + 5 = 14

Checking with a cut: cut {A→T, B→T} has capacity 4 + 10 = 14. The flow found (14) equals a cut's capacity (14), so both are optimal. The theorem guarantees the flow can't be more than any cut, so meeting one proves optimality.

This is how you find the real bottleneck of a network: the min cut, not the slowest individual link. Here S→B (5) is the smallest link, but the true limit is the 14 Mbit/s into T. It's also the maths of DDoS capacity planning (the min cut between the internet and your origin is the most attack traffic you can absorb), datacenter fabric design and multi-path TCP scheduling.

Menger's theorem, the unit-capacity special case: the number of link-disjoint paths between two nodes equals the minimum number of links whose failure disconnects them. "We have two disjoint paths to the DR site" and "no single link failure can isolate the DR site" are the same statement. For a full mesh of 4 routers, 3 disjoint paths between any pair means it survives any 2 link failures.

Spanning trees: STP, and how many there are

A spanning tree connects all V nodes with exactly V - 1 links and no loops. Ethernet needs one because broadcast frames loop forever in a cycle, and the Spanning Tree Protocol (STP) disables links until a tree remains. Kruskal's and Prim's algorithms find the minimum-cost spanning tree greedily. Their correctness rests on the cut property: the cheapest link crossing any cut is always safe to add.

How many spanning trees are there? Kirchhoff's matrix-tree theorem (1847) gives the answer from the graph Laplacian L = D - A of Ch. 11:

number of spanning trees = det( L with any one row and its column removed )

The count is a crude but real measure of how many ways a network can stay connected after failures, and it uses the same matrix whose λ₂ measured robustness in Ch. 11.

import numpy as np
def spanning_trees(edges, n):
    A = np.zeros((n, n))
    for i, j in edges:
        A[i, j] = A[j, i] = 1
    L = np.diag(A.sum(axis=1)) - A
    return round(np.linalg.det(L[1:, 1:]))

print(spanning_trees([(0,1), (1,2), (2,3), (3,0)], 4))                  # 4   ring
print(spanning_trees([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)], 4))         # 16  full mesh

Real-life engineering ties

• SWE: dependency graphs (build systems, package managers — a dependency cycle is a graph cycle-detection problem), org charts, state machines.
• AI: knowledge graphs, graph neural networks (GNNs), attention as a fully-connected weighted graph between tokens.
• Network: literally how routing works — network topology is a graph, OSPF/IS-IS is Dijkstra, BGP path selection is graph traversal with policy-weighted edges (Ch. 25).
• Security: attack graphs (modeling every path an attacker could take from initial foothold to target) are directed graphs, and finding the shortest/cheapest attack path is literally a Dijkstra/BFS problem; lateral-movement analysis in incident response is graph traversal over an access/trust graph.

More real-life examples:

• BGP, the routing protocol that holds the internet together, is a graph-based path-vector protocol — and BGP hijacking incidents (like the widely documented 2008 Pakistan Telecom incident that briefly took YouTube offline globally) happen because the graph has no built-in trust verification for advertised paths.
• Package managers (npm, pip, Cargo) and build systems (Bazel, Make) represent dependencies as a Directed Acyclic Graph (DAG) — a dependency cycle is a graph-cycle-detection bug, and build order is a topological sort of that DAG.
• Git's commit history is itself a DAG; commands like git log --graph, merge-base computation, and git bisect are all graph algorithms running directly on your repository.
• Service mesh tools (Istio, Linkerd) and distributed tracing platforms model microservice call patterns as a graph specifically to compute blast radius, critical-path latency, and single-point-of-failure analysis — all direct applications of this chapter.

Common mistake

Using Dijkstra on a graph with negative edge weights (it will produce silently wrong answers, not an error) — check for negative weights before choosing an algorithm.