Graph Algorithms

Introduction

This page covers four fundamental graph algorithms:

  • Breadth-first search and depth-first search, which explore everything reachable from a node;

  • Dijkstra’s algorithm, which finds shortest paths in a weighted graph;

  • Kruskal’s algorithm, which finds a cheapest way to connect every node.

Throughout, \(V\) is the number of nodes and \(E\) the number of edges. Graphs in sds list neighbors in edge insertion order, so every traversal below is reproducible, and the orders shown are exactly those the library produces.

Graph Traversals

Both traversals start from a source and visit each reachable node once. They share one skeleton and differ only in the container holding the frontier, the discovered nodes not yet explored:

Traversal

Frontier

Consequence

BFS

queue (FIFO)

explores in rings of increasing distance from the source

DFS

stack (LIFO)

follows one path as deep as possible, then backtracks

Running Example

Edges inserted in the order a–b, a–c, b–d, b–e, c–e, d–f:

        graph LR
    A((a)) --- B((b))
    A --- C((c))
    B --- D((d))
    B --- E((e))
    C --- E
    D --- F((f))

    style A fill:#3498db,color:#fff

Shortest Paths: Dijkstra

Problem

Given a graph with non-negative edge weights \(w(u, v) \ge 0\) and a source \(s\), find for every node \(v\) the distance

\[\delta(s, v) = \min_{\text{paths } p : s \leadsto v} \sum_{(x, y) \in p} w(x, y)\]

Algorithm

dist[s] <- 0; pred[s] <- None; push (0, s)
while heap not empty:
    (d, u) <- pop min
    if u settled: continue
    settle u
    for each edge (u, v, w):
        if d + w < dist[v]:                 # relaxation
            dist[v] <- d + w; pred[v] <- u; push (dist[v], v)

        graph LR
    S((s)) -- 10 --> T((t))
    S -- 5 --> Y((y))
    T -- 1 --> X((x))
    T -- 2 --> Y
    Y -- 3 --> T
    Y -- 9 --> X
    Y -- 2 --> Z((z))
    X -- 4 --> Z
    Z -- 7 --> S
    Z -- 6 --> X
Nodes in the order they are settled

Node

dist

Relaxations performed when settled

s

0

t ← 10, y ← 5

y

5

t ← 8 (was 10), x ← 14, z ← 7

z

7

x ← 13 (was 14)

t

8

x ← 9 (was 13)

x

9

—

Correctness

Invariant. When a node \(u\) is settled, dist[u] equals \(\delta(s, u)\).

Proof. Suppose \(u\) is the first node settled with dist[u] \(> \delta(s, u)\). Take a shortest path from \(s\) to \(u\) and let \((x, y)\) be its first edge leaving the settled set (\(x\) settled, \(y\) not). By the choice of \(u\), \(x\) was settled with its true distance, and relaxing \((x, y)\) gave \(\mathrm{dist}[y] = \delta(s, y)\). Weights are non-negative, so \(\delta(s, y) \le \delta(s, u) < \mathrm{dist}[u]\): \(y\) would have been popped before \(u\), a contradiction.

The argument uses \(w \ge 0\) exactly once, to say that the rest of the path cannot decrease the distance. With negative weights it breaks, which is why dijkstra() raises ValueError when it meets one.

Cost

Each edge is examined at most once from each endpoint, when that endpoint is settled, pushing at most one heap entry; each heap operation costs \(O(\log E) = O(\log V)\):

\[T = O\big((V + E) \log V\big)\]

This bound needs the outgoing edges of a node in \(O(\deg u)\), which outgoing_edges() provides; scanning every edge of the graph at each step would cost \(O(V \cdot E)\).

Minimum Spanning Trees: Kruskal

Problem

A spanning tree of a connected undirected graph is a subset of \(V - 1\) edges connecting every node without a cycle. A minimum spanning tree (MST) has the smallest total weight. On a graph with \(C\) connected components, one MST per component forms a minimum spanning forest of \(V - C\) edges; kruskal() returns that.

        graph LR
    A((a)) -- 4 --- B((b))
    A -- 8 --- H((h))
    B -. 8 .- C((c))
    B -. 11 .- H
    C -- 7 --- D((d))
    C -- 4 --- F((f))
    C -- 2 --- I((i))
    D -- 9 --- E((e))
    D -. 14 .- F
    E -. 10 .- F
    F -- 2 --- G((g))
    G -- 1 --- H
    G -. 6 .- I
    H -. 7 .- I

The classic example above (CLRS figure 23.1) has an MST of weight 37; dotted edges are left out. Two edges weigh 8 (a–h and b–c) and either completes a minimum tree; kruskal() keeps a–h because it was inserted first and the edge sort is stable.

Algorithm

F <- forest of the V nodes, no edge
for (u, v, w) in edges sorted by w:        # stable sort
    if find(u) != find(v):                  # different trees
        add (u, v, w) to F; union(u, v)

A disjoint-set structure (sds.advanced.DisjointSet) tracks which tree each node belongs to, in near-constant amortized time per operation.

Correctness: the Cut Property

Cut property. For any partition of the nodes into two groups \((S, V \setminus S)\), a lightest edge crossing the partition belongs to some minimum spanning tree.

Proof (exchange argument). Let \(e\) be a lightest crossing edge and \(T\) an MST without \(e\). Adding \(e\) to \(T\) closes a cycle, which must cross the partition a second time through some edge \(e'\). Then \(T' = T + e - e'\) is a spanning tree and \(w(T') = w(T) + w(e) - w(e') \le w(T)\), so \(T'\) is also an MST, and it contains \(e\).

When Kruskal adds an edge \((u, v)\), take \(S\) to be the tree containing \(u\). No edge crossing this cut has been kept yet, and all lighter edges have been examined already: \((u, v)\) is a lightest crossing edge, safe by the cut property. Edges joining two nodes of the same tree would close a cycle and are rightly skipped.

Cost

Sorting dominates:

\[T = O(E \log E) + O(E\, \alpha(V)) = O(E \log V)\]

since \(E \le V^2\) gives \(\log E \le 2 \log V\), and \(\alpha\) (inverse Ackermann) is at most 4 for any practical size.

Summary

Algorithm

Paradigm

Time

Requirement

bfs

graph search

\(O(V + E)\)

any graph

dfs

graph search

\(O(V + E)\)

any graph

dijkstra

greedy

\(O((V + E) \log V)\)

non-negative weights

kruskal

greedy

\(O(E \log V)\)

undirected weighted graph

References