Algorithms II

Vertices and Edges

A graph $G = (V, E)$ consists of a set of vertices (nodes) $V$ and a set of edges (arcs) $E \subseteq V \times V$. We only consider finite graphs where $|V|$ and $|E|$ are finite.

Directed graphs have ordered pairs $(u, v) \in E$, drawn with an arrow from $u$ (tail) to $v$ (head). $u$ is the source and $v$ the destination of the edge. Undirected graphs have unordered pairs (or the edge relation is symmetric); an undirected edge $\{u, v\}$ is conceptually equivalent to having both directed edges $(u, v)$ and $(v, u)$.

A simple graph has no self-loops (edges from a vertex to itself: $(v, v)$) and no parallel edges (multiple edges between the same ordered pair of vertices). Unless stated otherwise, the syllabus deals with simple graphs. A multigraph allows parallel edges; a pseudograph also allows self-loops.

A weighted graph associates a real number with each edge via a function $w: E \to \mathbb{R}$. Weights represent cost, distance, time, capacity, or any additive metric. Unweighted graphs can be considered as having unit weight on every edge.

Degree

The degree $\deg(v)$ of a vertex in an undirected graph is the number of edges incident at that vertex. In directed graphs:

• In-degree $\deg^{-}(v)$: number of edges entering $v$.
• Out-degree $\deg^{+}(v)$: number of edges leaving $v$.

Handshaking lemma: For an undirected graph, $\sum_{v \in V} \deg(v) = 2|E|$. For directed graphs, $\sum \deg^{-}(v) = \sum \deg^{+}(v) = |E|$. A corollary: the number of odd-degree vertices in any undirected graph is always even.

Paths, Walks, and Cycles

A walk is any sequence of vertices where consecutive pairs are edges. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices (except possibly the first/last). A simple path has no repeated vertices at all. The length of an unweighted path is the number of edges traversed ($k-1$ for $k$ vertices). For weighted graphs, the path length is the sum of edge weights along the path.

A cycle (or circuit) is a path of length at least 1 that starts and ends at the same vertex with no other vertex repeated. A graph with no cycles is acyclic.

Connectivity

An undirected graph is connected if there exists a path between every pair of vertices. A connected component is a maximal connected subgraph. The components partition the vertex set.

For directed graphs, we distinguish:

• Weak connectivity: the underlying undirected graph (ignoring edge directions) is connected.
• Strong connectivity: for every ordered pair $(u, v)$, there is a directed path from $u$ to $v$.

Subgraphs

• Subgraph: $G' = (V', E')$ with $V' \subseteq V$ and $E' \subseteq E$.
• Induced subgraph: select $V' \subseteq V$ and include all edges from $E$ whose both endpoints are in $V'$.
• Spanning subgraph: $V' = V$ (contains all vertices, subset of edges).

Trees and Forests

A free tree (or simply tree) is a connected, acyclic undirected graph. Equivalent characterisations for a graph with $n$ vertices:

1. Connected and has exactly $n-1$ edges.
2. Acyclic and has exactly $n-1$ edges.
3. Any two vertices are connected by exactly one simple path.
4. Connected, and removing any edge disconnects the graph (minimally connected).
5. Acyclic, and adding any edge creates exactly one cycle (maximally acyclic).

A forest is an acyclic undirected graph (a collection of disjoint trees). A forest with $c$ components has $n-c$ edges.

Density

A complete graph has $|E| = \binom{n}{2} = \frac{n(n-1)}{2}$. Most real-world graphs are sparse.

Example

Consider a road network: Cambridge (C), Oxford (O), London (L), York (Y). Roads: C—O (80), C—L (55), L—Y (210).

• $V = \{C, O, L, Y\}$, $|V|=4$. $E = \{(C,O), (C,L), (L,Y)\}$, $|E|=3$.
• $\deg(C)=2$, $\deg(O)=1$, $\deg(L)=2$, $\deg(Y)=1$.
• The graph is connected but not complete (missing 3 possible edges).
• $|E| = 3 = O(4)$, so it is sparse.

Summary

Past paper questions: y2025p1q9 (connected components, BFS on adjacency matrix).

Two Standard Representations

There are two fundamental ways to store a graph in memory. The choice of representation directly affects the asymptotic running time of graph algorithms, so understanding the trade-offs is critical for both implementation decisions and exam questions.

Adjacency Matrix

An adjacency matrix is a $|V| \times |V|$ matrix $M$. For unweighted graphs:

$M[u][v] = \begin{cases} 1 & \text{if } (u, v) \in E \\ 0 & \text{otherwise} \end{cases}$

For weighted graphs, $M[u][v]$ stores the edge weight (and typically $\infty$, 0, or some sentinel for absent edges). For undirected graphs, the matrix is symmetric: $M[u][v] = M[v][u]$. This means only the upper or lower triangle needs to be stored explicitly, roughly halving the memory. For unweighted graphs, each entry can be a single bit.

Space: $\Theta(|V|^2)$ regardless of the number of edges. Even a graph with zero edges allocates a full matrix.

Key operations:

• Test if $(u, v) \in E$: $O(1)$ — single array lookup.
• List all neighbours of vertex $u$: $\Theta(|V|)$ — must scan the entire row $u$.
• Iterate over all edges: $\Theta(|V|^2)$ — must visit every matrix cell.
• Add or remove an edge: $O(1)$ — set or clear a cell.

Adjacency Lists

An array $A$ of length $|V|$, where $A[u]$ points to a linked list or dynamic array containing all $v$ such that $(u, v) \in E$. For weighted graphs, each list entry stores $(v, w(u,v))$.

Space: $\Theta(|V| + |E|)$. Each directed edge contributes one list entry. For undirected graphs, each edge appears in two lists, so space is $\Theta(|V| + 2|E|) = \Theta(|V| + |E|)$.

Key operations:

• Test if $(u, v) \in E$: $O(\deg(u))$ — sequential scan of $u$‘s list. Worst case $O(|V|)$ when $\deg(u) = |V|-1$.
• List neighbours of $u$: $\Theta(\deg(u))$ — exactly the list length.
• Iterate over all edges: $\Theta(|V| + |E|)$ — visit each list head and each entry once.
• Add edge: $O(1)$ (prepend to list). Remove edge: $O(\deg(u))$ (find and delete).
• For undirected graphs, removal must be done from both endpoints’ lists: $O(\deg(u) + \deg(v))$.

Worked Example

Directed weighted graph: $V = \{1, 2, 3, 4\}$, edges $(1,2)$ weight 5, $(1,3)$ weight 2, $(2,4)$ weight 1.

Matrix representation: $\begin{pmatrix} 0 & 5 & 2 & \infty \\ \infty & 0 & \infty & 1 \\ \infty & \infty & 0 & \infty \\ \infty & \infty & \infty & 0 \end{pmatrix}$

Adjacency list representation:

• $A[1] \to (2,5) \to (3,2)$
• $A[2] \to (4,1)$
• $A[3] \to \emptyset$
• $A[4] \to \emptyset$

Space analysis: matrix uses $4 \times 4 = 16$ entries. Lists use 3 list entries + 4 array slot pointers = 7 entries. For this sparse graph ($|E|=3$ of a possible 12), lists are significantly more compact.

Trade-off Summary

Impact on Graph Algorithms

BFS/DFS: With adjacency lists, both run in $\Theta(|V| + |E|)$ because the inner loop visits each neighbour exactly once. With an adjacency matrix, the inner loop must scan all $|V|$ columns for each dequeued/extracted vertex, costing $\Theta(|V|)$ per vertex. Total: $O(|V|^2)$ regardless of edge count.

Exam point (y2025p1q9): Tight bounds for BFS with adjacency matrix are $\Omega(|V|^2)$ and $O(|V|^2)$; with lists, $\Omega(|V|+|E|)$ and $O(|V|+|E|)$.

Dijkstra: With binary heap and adjacency lists: $O((|V|+|E|)\log |V|)$. With matrix: neighbour iteration becomes $\Theta(|V|)$ per vertex, and using a simple array instead of heap gives $O(|V|^2)$, which can be faster than $O(|V|^2 \log |V|)$ for dense graphs due to lower constants.

Floyd-Warshall: Inherently uses a matrix (the distance matrix itself), running in $\Theta(|V|^3)$. Johnson’s algorithm relies on adjacency lists for sparsely efficient Dijkstra calls.

Summary

Past paper questions: y2025p1q9(a)(i) (BFS complexity bounds with adjacency matrix).

The Seven Bridges Problem

In 1736, Leonhard Euler considered the city of Königsberg (now Kaliningrad), which straddled the Pregel River. Seven bridges connected four landmasses (two riverbanks and two islands). The puzzle: could a citizen walk through the city, crossing every bridge exactly once, and return to the starting point?

Euler’s key insight was to abstract away geography: landmasses become vertices, bridges become edges. This produced the first formal graph-theoretic argument in history. Euler proved no such walk exists: the four landmasses have degrees 3, 3, 3, and 5 (all odd), making an Eulerian circuit impossible. Beyond solving a puzzle, Euler established graph theory as a mathematical discipline.

Eulerian Paths and Circuits

An Eulerian path (or trail) visits every edge in the graph exactly once; vertices may be revisited. An Eulerian circuit (or tour) is an Eulerian path that starts and ends at the same vertex.

Theorem (undirected graphs): A connected, undirected graph has an Eulerian circuit iff every vertex has even degree. It has an Eulerian path but not a circuit iff exactly zero or two vertices have odd degree; if two, the path must start at one odd-degree vertex and end at the other. If more than two vertices have odd degree, no Eulerian path exists.

Directed version: An Eulerian circuit exists iff every vertex has in-degree equal to out-degree and the graph is strongly connected (ignoring isolated vertices). An Eulerian path (start ≠ end) exists iff exactly one vertex has out-degree $=$ in-degree $+ 1$ (start), one vertex has in-degree $=$ out-degree $+ 1$ (end), and all other vertices have in-degree $=$ out-degree.

Proof Sketch: Necessity

In an Eulerian circuit, every time the walk enters a vertex (except the start/end) it must also leave via a different edge. Thus each visit consumes two incident edges, one for entry and one for exit. For the circuit to cover every edge exactly once, each vertex must have an even number of incident edges in total. If the walk is a path from $a$ to $b$ ($a \neq b$), vertex $a$ has one more exit than entry, $b$ has one more entry than exit, and all others are balanced, giving exactly two odd-degree vertices.

Sufficiency: If all degrees are even, construct the circuit by greedily following unused edges from the current vertex. When stuck (returned to start), you have a closed trail. Remove those edges; the remaining subgraph still has all even degrees. Recursively find circuits in each connected component and splice them into the main circuit at shared vertices. This construction is called Hierholzer’s algorithm and runs in $\Theta(|V| + |E|)$.

Worked Example 1: Königsberg

Landmasses: two riverbanks (north, south), two islands (Kneiphof, Lomse). Bridges: 5 connect to Kneiphof, 3 to the north bank, 3 to the south bank, 3 to Lomse. In the graph, every vertex has odd degree (3, 3, 3, 5). Since all are odd, Euler’s theorem says no Eulerian circuit or path exists. The problem is impossible.

Worked Example 2: Modified Bridge Network

Suppose one bridge is added between the two riverbanks, making degrees: 4, 4, 3, 3. Now exactly two vertices have odd degree (3). An Eulerian path exists, starting at one odd-degree vertex and ending at the other.

Worked Example 3: Simple Abstract Graph

Graph with vertices $\{A,B,C,D\}$ and edges: $\{A,B\}, \{A,C\}, \{B,C\}, \{B,D\}, \{C,D\}$ (five edges). Degrees: $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=3$, $\deg(D)=2$. Exactly two odd-degree vertices (B and C). Eulerian path: $B \to A \to C \to D \to B \to C$. No circuit exists (B and C are odd).

Graph Invariants

The parity of vertex degrees (the count of odd-degree vertices) is a graph invariant preserved under isomorphism. In Königsberg, the parity multiset is $\{3,3,3,5\}$, all odd; no isomorphic graph with all even degrees can exist. This is an early example of an invariant proof: properties preserved by isomorphism can be used to prove non-isomorphism.

Modern Applications

• Chinese Postman Problem: Find the shortest closed walk covering every edge at least once. Solved by identifying odd-degree vertices, computing a minimum-weight perfect matching among them (to determine which edges to duplicate), then finding an Eulerian circuit. Runs in $O(|V|^3)$ due to the matching step. Applications in postal delivery, street sweeping, and gritting routes.
• DNA fragment assembly (de Bruijn graphs): Sequencing produces short overlapping reads (k-mers). A de Bruijn graph is built where edges represent k-mers and vertices represent (k-1)-mer overlaps. An Eulerian path through this graph reconstructs the original genome sequence. This scales much better than Hamiltonian-path alternatives for large genomes.
• PCB testing: Test probes must traverse every trace on a circuit board exactly once; this is an Eulerian path problem.
• Snow plough routing: After a snowfall, every street must be ploughed; the problem reduces to Eulerian circuit construction on a multigraph (multiple lanes per road).

Key Distinction

• Eulerian: visits every edge exactly once. Solvable in $\Theta(|V| + |E|)$.
• Hamiltonian: visits every vertex exactly once. NP-complete in general; no efficient algorithm is known.

Do not confuse these two in exam answers.

Summary

Past paper questions: Not a heavily examined standalone topic, but graph invariants and parity arguments appear in proofs. Connected components and BFS are related exam topics (y2025p1q9).

Directed Acyclic Graphs (DAGs)

A DAG is a directed graph containing no directed cycles. Many real-world dependency structures are naturally acyclic: course prerequisites, build system targets (make), version histories.

Existence of sources and sinks: Every DAG has at least one source (in-degree 0) and at least one sink (out-degree 0). Proof: pick any vertex and follow incoming edges backward. Since there are no cycles and the graph is finite, this walk must terminate at a source. Symmetrically, following outgoing edges forward reaches a sink. This property is used in the source-removal topological sort algorithm.

Topological ordering: A linear ordering exists such that all edges go left to right iff the graph is a DAG. See topological sort for the full algorithm.

SSSP on DAGs: Relax edges in topological order. Correctness: when vertex $u$ is processed, all incoming paths to $u$ have already been considered because all predecessors appear earlier in the topological order. Thus one pass suffices. Running time: $\Theta(|V| + |E|)$, even with negative edge weights (provided no cycles exist, which they cannot in a DAG). This is the fastest SSSP algorithm amongst those covered.

Longest path on DAGs: By negating all edge weights, or replacing $\min$ with $\max$ during relaxation, the longest path can also be found in $\Theta(|V| + |E|)$. For general graphs, the longest path problem is NP-hard; DAGs are a notable exception.

Bipartite Graphs

A graph is bipartite if its vertex set can be partitioned into two disjoint sets $L$ and $R$ such that every edge has one endpoint in each set. No edges exist within $L$ or within $R$.

Characterisation: An undirected graph is bipartite iff it contains no cycle of odd length. A graph with a triangle ($K_3$) is never bipartite; a tree is always bipartite.

Testing bipartiteness (BFS-based algorithm):

1. Pick any unvisited vertex, colour it BLACK.
2. Run BFS from it. Colour each vertex at distance $d$: BLACK if $d$ is even, RED if $d$ is odd (alternating by parity).
3. Scan all edges. If any edge connects two vertices of the same colour, an odd cycle exists — the graph is not bipartite.
4. Repeat for each connected component until all vertices are processed.

Both colouring and conflict checking run in $O(|V|+|E|)$, so the full test is $\Theta(|V|+|E|)$. BFS’s distance-level property guarantees the alternating colour assignment is correct: vertices at the same BFS level cannot be adjacent in a bipartite graph.

Worked example: 4-cycle: $V = \{1,2,3,4\}$, $E = \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}\}$. BFS from 1: dist(1)=0 (BLACK), dist(2)=dist(4)=1 (RED), dist(3)=2 (BLACK). No conflict — bipartite with $L=\{1,3\}$, $R=\{2,4\}$.

Worked non-example: Triangle $K_3$: $V=\{1,2,3\}$, $E=\{\{1,2\},\{2,3\},\{3,1\}\}$. BFS from 1: dist(1)=0 (BLACK), dist(2)=dist(3)=1 (RED). Edge $\{2,3\}$ connects two RED vertices — conflict, not bipartite.

Applications: Matching problems (assigning students to rooms, workers to tasks) are modelled as bipartite graphs. Maximum bipartite matching reduces to a max-flow problem and can be solved with Ford-Fulkerson or Hopcroft-Karp.

Complete Graphs

The complete graph $K_n$ has all $\binom{n}{2}$ possible edges; every vertex has degree $n-1$. $K_n$ is $(n-1)$-regular. A clique is any complete induced subgraph.

Trees (Detailed)

For an undirected graph on $n$ vertices, the following are equivalent definitions of a tree:

1. Connected and acyclic.
2. Connected and has exactly $n-1$ edges.
3. Acyclic and has exactly $n-1$ edges.
4. Between any two vertices, exactly one simple path exists.
5. Maximally acyclic: adding any edge creates exactly one cycle.
6. Minimally connected: removing any edge disconnects the graph.

Every tree with $n \ge 2$ has at least two leaves (vertices of degree 1). A rooted tree designates one vertex as root; parent and child relationships emerge from distances to the root. The depth of a vertex is its distance from the root. A binary tree restricts each vertex to at most two children. Every tree is bipartite (alternate levels).

Transpose, Complement, and Square

• Transpose $G^T$: reverses all edges. $(u,v) \in E \iff (v,u) \in E^T$. Essential for Kosaraju’s algorithm.
• Complement $\overline{G}$: same vertices, $(u,v) \in E(\overline{G})$ iff $(u,v) \notin E(G)$. A clique in $G$ is an independent set in $\overline{G}$.
• Square $G^2$: edge $(u,v)$ exists iff a path of length $\le 2$ connects them in $G$.

Summary

Past paper questions: y2026p1q10 (DAG, topological sort, transitive closure for DAGs), y2025p1q9(b)(i) (connected components labelling).

Overview

Breadth-First Search (BFS) explores vertices in order of increasing distance from a source vertex $s$. It uses a FIFO queue to manage the frontier. BFS discovers every vertex reachable from $s$ and computes the shortest-path distance (in terms of number of edges) for unweighted graphs.

Colour Scheme

BFS uses three colours to track vertex state:

• White: undiscovered (initial state for all vertices).
• Grey: discovered but not yet fully explored (currently in or awaiting processing from the queue).
• Black: finished; all neighbours have been examined.

These colours prevent enqueuing the same vertex twice — a key distinction from naive tree traversal. Without the pending/grey marker, a vertex could be enqueued multiple times, wasting memory and time.

Pseudocode

BFS(G, s):
  for each v in G.V:
    v.colour = WHITE
    v.d = ∞             // distance from source
    v.π = NIL            // predecessor
  s.colour = GREY
  s.d = 0
  s.π = NIL
  Q = new Queue()
  ENQUEUE(Q, s)
  while Q not empty:
    u = DEQUEUE(Q)
    for each v in G.Adj[u]:
      if v.colour == WHITE:
        v.colour = GREY
        v.d = u.d + 1
        v.π = u
        ENQUEUE(Q, v)
    u.colour = BLACK

How It Works

The queue stores the frontier: vertices discovered but whose neighbours have not yet been examined. Because vertices are enqueued in order of discovery (and thus by distance), BFS explores distance $k$ vertices before any distance $k+1$ vertex.

The predecessor array $\pi$ implicitly defines a breadth-first tree: the edges $(v.\pi, v)$ for all $v$ with $v.\pi \neq \text{NIL}$ form a tree rooted at $s$. Following $\pi$ pointers backwards from any vertex reconstructs a shortest path to $s$.

Worked Example

Consider an undirected graph with $V = \{A,B,C,D,E\}$ and edges: $A-B$, $A-C$, $B-D$, $C-D$, $D-E$. Source $s = A$.

Predecessor tree: $\pi(B)=A$, $\pi(C)=A$, $\pi(D)=B$ (first visit), $\pi(E)=D$. Shortest path A→E: E→D→B→A (reverse gives A-B-D-E, distance 3).

Complexity Analysis

With adjacency lists: the initialisation loop and the outer while loop touch each vertex once ($\Theta(|V|)$). The inner for loop traverses each edge’s adjacency list entry at most once ($\Theta(|E|)$ for directed, at most $2|E|$ for undirected). Total: $\Theta(|V| + |E|)$.

With adjacency matrix: the inner loop must scan all $|V|$ columns for each dequeued vertex to check if an edge exists. This costs $\Theta(|V|)$ per vertex, giving $O(|V|^2)$ overall. For sparse graphs this is significantly worse.

Key Point: Duplicate Enqueue Prevention

A naive implementation that checks only marked at dequeue time (not at enqueue) can insert the same vertex into the queue multiple times. The GREY/pending flag prevents this: once a vertex is discovered, its colour changes to grey immediately, so subsequent edges to it are ignored.

Summary

Past paper questions: y2025p1q9(a)(i) (BFS time bounds with adjacency matrix).

What We Need to Prove

When BFS terminates, for every vertex $v$ reachable from source $s$, the value $v.d$ equals the true shortest-path distance $\delta(s, v)$ (the minimum number of edges on any path from $s$ to $v$). For unreachable vertices, $v.d = \delta(s, v) = \infty$. Additionally, following predecessor $\pi$ pointers backwards from any vertex reconstructs a shortest path to $s$.

The proof proceeds through three lemmas, culminating in a contradiction argument that no vertex can be the “first” to receive a wrong distance.

Lemma 1: Upper Bound on Neighbour Distance

If $(u, v) \in E$, then $\delta(s, v) \le \delta(s, u) + 1$.

Proof: If $u$ is unreachable from $s$, then $\delta(s, u) = \infty$ and the inequality trivially holds. If $u$ is reachable, the shortest path to $v$ is at most the shortest path to $u$ plus one more edge $(u, v)$. It cannot be longer than that (though it could be shorter if there is a path to $v$ that bypasses $u$). Hence the inequality.

Lemma 2: $v.d$ Never Underestimates

On termination, for all $v \in V$, we have $v.d \ge \delta(s, v)$.

Proof by induction on the number of enqueue operations:

Base case: Immediately before the while loop begins: $s.d = 0 = \delta(s, s)$, so the hypothesis holds for $s$. For all other vertices, $v.d = \infty \ge \delta(s, v)$, even if unreachable. Hypothesis holds.

Inductive step: The while/for loops only change $v.d$ when $v$ is white (not pending), via the assignment $v.d = u.d + 1$. By the induction hypothesis, $u.d \ge \delta(s, u)$. Then: $v.d = u.d + 1 \ge \delta(s, u) + 1 \ge \delta(s, v)$ where the last inequality is Lemma 1. Since $v.d$ is never changed again (it becomes grey immediately), the property persists.

This lemma says the algorithm never reports a distance too low; it may overestimate until convergence.

Lemma 3: Queue Disciplines the Order

Queue property $\phi$: If the queue is $Q = v_1, v_2, \ldots, v_x$ (head to tail), then $v_x.d \le v_1.d + 1$ and the $v.d$ values are non-decreasing from head to tail: $v_i.d \le v_{i+1}.d$ for all $i = 1, \ldots, x-1$.

Proof by induction on queue operations.

• Dequeue: Removing $v_1$ leaves $v_2$ as the new head. From $\phi$ we have $v_x.d \le v_1.d + 1 \le v_2.d + 1$ (since $v_1.d \le v_2.d$). So $\phi$ holds after dequeue.
• Enqueue: When $v$ (with $v.d = u.d + 1$) is appended, we need to verify $v_1.d \le \cdots \le v_x.d \le v.d$ and $v.d \le v_1.d + 1$. The first holds because $v_x.d \le u.d + 1$ (from $\phi$ before dequeue, $v_x.d \le v_1.d (= u.d) + 1 = u.d+1 = v.d$). The second holds because $v.d = u.d + 1 = v_1.d + 1$.

Corollary: If vertex $a$ is enqueued before vertex $b$, then $a.d \le b.d$ on termination. This follows from the non-decreasing property when $a$ and $b$ are simultaneously in the queue and from transitivity of $\le$ when they are not.

Termination: Proof by Contradiction

Assume the algorithm errs. Let $v$ be the vertex with minimum $\delta(s, v)$ whose $v.d \neq \delta(s, v)$. By Lemma 2, we must have $v.d > \delta(s, v)$. Also $v \neq s$ (since $s.d = 0$ is correct), and $v$ must be reachable from $s$ (otherwise $\delta(s,v) = \infty \ge v.d$).

Let $u$ be the immediate predecessor of $v$ on a true shortest path $s \leadsto v$. Then $\delta(s, u) = \delta(s, v) - 1$. Since $\delta(s, u) < \delta(s, v)$ and $v$ is the minimum-$\delta$ vertex with a wrong $d$, we have $u.d = \delta(s, u)$. Hence: $v.d > \delta(s, v) = \delta(s, u) + 1 = u.d + 1$

Now consider the moment $u$ was dequeued from $Q$. Vertex $v$ was in exactly one of three states:

1. Not yet enqueued (white): The inner loop would explore the edge $(u, v)$ and set $v.d = u.d + 1$. But we have $v.d > u.d + 1$ — contradiction.
2. In the queue (grey, pending): $v$ was enqueued earlier by some $w$ with $v.d = w.d + 1$. By the corollary, $w.d \le u.d$ (since $w$ was enqueued before $u$ was dequeued, and $u$ was dequeued before $v$, so $w \le u \le v$ in dequeue order). Thus $v.d = w.d + 1 \le u.d + 1$, contradicting $v.d > u.d + 1$.
3. Already dequeued (black): By the corollary, $v.d \le u.d$, contradicting $v.d > u.d + 1$.

All three cases produce contradictions. Therefore no such $v$ exists; BFS computes correct distances for all vertices.

Shortest-Path Tree

The predecessor subgraph $G_\pi = (V_\pi, E_\pi)$ where $V_\pi = \{v \mid v.\pi \neq \text{NIL}\} \cup \{s\}$ and $E_\pi = \{(\pi[v], v) \mid v \in V \setminus \{s\}\}$ forms a breadth-first tree. It is a tree because each vertex (except $s$) has exactly one predecessor and no cycles exist. The unique path in $G_\pi$ from $s$ to any reachable $v$ is a shortest path in $G$.

Applications

Summary

Past paper questions: y2025p1q9(a)(i) (BFS time analysis with different representations).

Overview

Depth-First Search (DFS) explores as deeply as possible along each branch before backtracking. It is typically implemented recursively (the call stack acts as the LIFO stack). DFS produces a depth-first forest and assigns two integer timestamps per vertex: discovery time and finish time.

Unlike BFS, DFS does not require a source vertex; it discovers all vertices in the graph by restarting from any unvisited vertex until all have been explored.

Pseudocode

DFS(G):
  for each v in G.V:
    v.colour = WHITE
    v.π = NIL
  time = 0
  for each v in G.V:
    if v.colour == WHITE:
      DFS-VISIT(G, v)

DFS-VISIT(G, u):
  time = time + 1
  u.d = time              // discovery time
  u.colour = GREY
  for each v in G.Adj[u]:
    if v.colour == WHITE:
      v.π = u
      DFS-VISIT(G, v)
  u.colour = BLACK
  time = time + 1
  u.f = time              // finish time

Timestamps

Each vertex gets two timestamps:

• $d[v]$ (discovery time): when the vertex is first encountered (colour changes white → grey).
• $f[v]$ (finish time): when all descendants have been explored (colour changes grey → black).

Timestamps are integers from 1 to $2|V|$. Every vertex is discovered exactly once and finished exactly once.

Worked Example

Consider a directed graph: $V = \{1,2,3,4,5,6,7,8\}$ with edges: $1 \to 2$, $1 \to 3$, $2 \to 3$, $2 \to 4$, $3 \to 5$, $4 \to 5$, $5 \to 6$, $5 \to 8$, $6 \to 7$, $7 \to 6$, $8 \to 4$.

Run DFS starting from vertex 1 (assume adjacency lists in numerical order):

The timestamps reveal ancestry: vertex 2 is a descendant of 1 because $d[1]=1 < d[2]=2 < f[2]=15 < f[1]=16$.

Parenthesis Theorem

For any two vertices $u$ and $v$, exactly one of the following holds:

1. $[d[u], f[u]]$ and $[d[v], f[v]]$ are disjoint: neither is an ancestor of the other.
2. $[d[u], f[u]]$ is fully contained within $[d[v], f[v]]$: $u$ is a descendant of $v$.
3. $[d[v], f[v]]$ is fully contained within $[d[u], f[u]]$: $v$ is a descendant of $u$.

This theorem implies: $v$ is a proper descendant of $u$ in the depth-first forest iff $d[u] < d[v] < f[v] < f[u]$.

Complexity

$\Theta(|V| + |E|)$ with adjacency lists. Each vertex is discovered once, and the for loop in DFS-VISIT iterates over each adjacency list entry exactly once (or twice for undirected graphs). With an adjacency matrix, the cost becomes $\Theta(|V|^2)$.

DFS Forest

When DFS restarts from an unvisited vertex in the outer loop, it begins a new tree. The set of all trees forms the depth-first forest. For an undirected graph, the number of DFS trees equals the number of connected components.

Comparison: BFS vs DFS

Summary

Past paper questions: y2026p1q10 (topological sort via DFS), y2025p1q9(b)(i) (connected components).

Four Edge Types

During DFS on a directed graph, every edge $(u, v)$ is classified based on the colour of the target vertex $v$ at the moment the edge is first explored from $u$. There are four classifications:

1. Tree edge: $v$ is WHITE. The edge is added to the DFS forest; $v$ becomes a child of $u$ in the depth-first tree. Discovered during: DFS-VISIT(u) → v.colour == WHITE → call DFS-VISIT(v).
2. Back edge: $v$ is GREY. $v$ is an ancestor of $u$ in the current DFS tree. Indicates a directed cycle exists. Example: $u \to \text{ancestor}(u)$.
3. Forward edge: $v$ is BLACK and is a descendant of $u$ in the DFS forest (but not a direct child; direct children are tree edges). Connects a vertex to a non-child descendant.
4. Cross edge: $v$ is BLACK and is neither an ancestor nor a descendant of $u$. Either connects different subtrees of the same DFS tree, or connects vertices in different DFS trees entirely.

The classification depends on DFS exploration order: the same edge might be classified differently if adjacency lists are processed in a different order.

Timestamp-Based Characterisation

The timestamps give precise, colour-independent criteria. For edge $(u, v)$:

• Tree or forward edge iff $d[u] < d[v] < f[v] < f[u]$. The target’s interval is nested inside the source’s. To distinguish tree from forward: for tree edges, $v$ was discovered via this specific edge; for forward edges, $v$ was discovered through a different path but is still a descendant.
• Back edge iff $d[v] \le d[u] < f[u] \le f[v]$. The target was discovered before the source and finishes after the source. This is the hallmark of cycles.
• Cross edge iff $d[v] < f[v] < d[u] < f[u]$. The entire interval of $v$ lies before the entire interval of $u$.

Properties Through an Example Walk

Run DFS on this directed graph: $1 \to 2$, $1 \to 3$, $2 \to 3$, $2 \to 4$, $3 \to 5$, $4 \to 5$, $5 \to 6$, $6 \to 7$, $7 \to 6$, $5 \to 8$, $8 \to 4$.

Discovery and finish times (assuming adjacency lists in numerical order, starting from 1):

Classify each edge:

• $(1,2)$: tree (2 white). $(1,3)$: forward (3 black, descendant: $d[1] < d[3] < f[3] < f[1]$, but 3 discovered via 2, not 1).
• $(2,3)$: tree. $(2,4)$: tree.
• $(3,5)$: tree.
• $(4,5)$: forward (5 discovered later via 3, but is descendant of 4).
• $(5,6)$: tree. $(5,8)$: tree.
• $(6,7)$: tree.
• $(7,6)$: back (6 is grey when exploring $7 \to 6$; also $d[6]=6 \le d[7]=8$, $f[6]$ is not assigned yet but $f[7] < f[6]$ — back edge).
• $(8,4)$: back (4 is grey when exploring $8 \to 4$; or by timestamps: $d[4]=4 \le d[8]=9$ and $f[8]$ is not yet assigned before $8$ finishes, but $f[4]=7 < f[8]=13$ — confirms ancestor relationship).

The presence of back edges $(7,6)$ and $(8,4)$ confirms cycles in the graph.

Undirected Graphs

In an undirected graph, DFS processes each edge in both directions (once from each endpoint). This restricts the possible classifications:

• Tree edges occur when the neighbour is white.
• Back edges occur when the neighbour is already discovered but is not the immediate parent (the vertex from which we just arrived). The edge $(v, \text{parent})$ explored in reverse is trivially a back edge under the directed definition; in the undirected context, we treat this as the reverse of the tree edge and not a cycle-indicating back edge.

Forward and cross edges cannot occur in undirected graphs. Proof: if $(u,v)$ were a forward edge (descendant), then exploring from $v$ would encounter $u$ as a back edge; but the symmetric relationship means the edge would already be part of the DFS tree. Cross edges would imply exploring from $u$ first then from $v$ later, but if $(u,v) \in E$, the second exploration would encounter the other vertex immediately, making it a back edge.

Conclusion for undirected graphs: Every edge is either a tree edge or a back edge. A back edge (to a non-parent ancestor) indicates an undirected cycle.

Cycle Detection

• Directed graph is a DAG iff DFS produces no back edges. Algorithm: run DFS; if any edge $(u, v)$ is explored with $v$ coloured GREY, report “contains cycle”. Time: $\Theta(|V| + |E|)$.
• Undirected graph has a cycle iff any non-tree back edge exists.

This is a fundamental result: DFS provides linear-time cycle detection for both directed and undirected graphs.

Summary

Past paper questions: y2026p1q10 (DAG and topological sort via DFS).

Definition

A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge $u \to v$, vertex $u$ appears before vertex $v$ in the ordering. A topological ordering exists iff the graph is a DAG (no directed cycles). If cycles exist, no such ordering is possible: a cycle $a \to b \to c \to a$ would require $a$ before $b$ before $c$ before $a$, a contradiction.

DFS-Based Algorithm

Run a full DFS on the graph. As each vertex finishes (colour changes from grey to black), prepend it to a list. The final list is a topological order.

Pseudocode:

TOPOLOGICAL-SORT(G):
  for each v in G.V:
    v.colour = WHITE
  L = empty list         // will hold result
  for each v in G.V:
    if v.colour == WHITE:
      DFS-VISIT-TOPO(G, v)
  return L

DFS-VISIT-TOPO(G, u):
  u.colour = GREY
  for each v in G.Adj[u]:
    if v.colour == GREY: report "cycle exists"
    if v.colour == WHITE:
      DFS-VISIT-TOPO(G, v)
  u.colour = BLACK
  prepend u to L

Running time: $\Theta(|V| + |E|)$ with adjacency lists.

Why Reverse Finish Time?

For any edge $u \to v$ in a DAG, DFS produces $f[v] < f[u]$. Proof: when $(u,v)$ is explored, $v$ cannot be grey (that would be a back edge → cycle, impossible in DAG). If $v$ is white, $v$ becomes a descendant of $u$, so $f[v] < f[u]$ by the parenthesis theorem. If $v$ is black, then $f[v] < d[u] < f[u]$, so again $f[v] < f[u]$. In all cases $v$ finishes before $u$. Sorting by decreasing $f[v]$ therefore places $u$ (later finish) before $v$ (earlier finish), satisfying $u \to v$.

Source-Removal Algorithm (Alternative)

An alternative approach repeatedly removes sources (vertices with in-degree 0):

TOPOLOGICAL-SORT-SOURCES(G):
  compute in-degree[v] for all v
  Q = queue of all vertices with in-degree 0
  L = []
  while Q not empty:
    u = DEQUEUE(Q)
    append u to L
    for each v in G.Adj[u]:
      in-degree[v] = in-degree[v] - 1
      if in-degree[v] == 0:
        ENQUEUE(Q, v)
  if |L| != |V|: graph has a cycle
  return L

Also $\Theta(|V| + |E|)$. This version is sometimes called Kahn’s algorithm and has the advantage of detecting cycles explicitly (if $|L| < |V|$, a cycle exists).

Worked Example

DAG with vertices $\{A,B,C,D,E\}$ and edges: $A \to B$, $A \to C$, $B \to D$, $C \to D$, $D \to E$.

DFS method: Run DFS starting from $A$:

• Visit $A$ (d=1), then $B$ (d=2), then $D$ (d=3), then $E$ (d=4). $E$ finishes (f=5), $D$ finishes (f=6), $B$ finishes (f=7). Back to $A$, visit $C$ (d=8), $C$ finishes (f=9). $A$ finishes (f=10).
• Finish times (decreasing): A(10), C(9), B(7), D(6), E(5).
• Topological order: $A, C, B, D, E$.

Source-removal method:

• Initial in-degrees: A=0, B=1, C=1, D=2, E=1.
• Pick A (indeg 0). Remove A: decrease B→0, C→0. Queue: [B, C]. Output: [A].
• Pick B. Remove B: decrease D→1. Queue: [C]. Output: [A,B].
• Pick C. Remove C: decrease D→0. Queue: [D]. Output: [A,B,C].
• Pick D. Remove D: decrease E→0. Queue: [E]. Output: [A,B,C,D].
• Pick E. Remove E. Output: [A,B,C,D,E].

Both methods produce valid topological orders (note: A, C, B differs from A, B, C — both are valid since B and C are incomparable).

Applications

• Task scheduling: tasks with prerequisites; topological order gives a valid execution sequence.
• Build systems: make uses topological sort to determine which targets to build first.
• Course prerequisite planning: courses with dependencies form a DAG.
• SSSP on DAGs: relaxing edges in topological order solves SSSP in $\Theta(|V|+|E|)$, even with negative edge weights (but no cycles).

Summary

Past paper questions: y2026p1q10 (topological sort algorithm, DAG transitive closure).

Problem Statement

Given a weighted, directed graph $G = (V, E)$ with weight function $w: E \to \mathbb{R}$ and a designated source vertex $s \in V$, find the shortest path (minimum total weight) from $s$ to every other vertex.

Shortest-path weight from $u$ to $v$:

$\delta(u, v) = \begin{cases} \displaystyle\min_{p: u \leadsto v} w(p) & \text{if a path exists} \\[8pt] \infty & \text{otherwise} \end{cases}$

where $w(p) = \sum_{i=1}^{k-1} w(v_i, v_{i+1})$ for path $p = v_1, v_2, \ldots, v_k$.

A shortest path from $u$ to $v$ is any path $p$ satisfying $w(p) = \delta(u, v)$. Shortest paths are not necessarily unique; there may be multiple paths with the same minimum weight.

Variants of Shortest-Path Problems

SDSP reduces to SSSP on $G^T$. SPSP has no known algorithm asymptotically faster than SSSP in the worst case. APSP can be solved by $|V|$ iterations of SSSP or by dedicated algorithms (Floyd-Warshall, Johnson).

Assumptions and Edge Cases

• No negative-weight cycles reachable from $s$. If a negative cycle is reachable, you can loop forever, decreasing path weight without bound: $\delta(s, v) = -\infty$ for any vertex on the cycle, and the problem is ill-defined.
• Positive-weight cycles are never part of a shortest path: removing such a cycle strictly reduces the total weight. Hence shortest paths can be assumed simple (no vertex repeated).
• Zero-weight cycles do not affect path weight; they can be removed without changing the result. So we assume shortest paths have at most $|V|-1$ edges.
• Distances are undefined (or $-\infty$) if a negative-weight cycle is reachable on the path to that vertex.

Optimal Substructure

Shortest paths exhibit optimal substructure: any subpath of a shortest path is itself a shortest path.

Proof: Let $p = v_1 \leadsto v_k$ be a shortest path, and let $v_i \leadsto v_j$ be any contiguous subpath. If there were a shorter path $p'$ from $v_i$ to $v_j$, replacing the subpath with $p'$ would produce a $v_1 \leadsto v_k$ path strictly shorter than $p$, contradicting optimality of $p$.