Module III — Graph Algorithms

← Back to Data Structures and Algorithms

Course: MAT5EJ302(1) — Data Structures and Algorithms
Hours: 12 | Textbook Sections: 3.4, 4.1–4.4, 4.5, 4.7 (Dasgupta et al.)

---

1. Checking Connectivity

A graph is connected if there is a path between every pair of vertices.

1.1 Connected Components via DFS

If the graph is not connected, it has multiple connected components — maximal subgraphs that are connected within themselves. DFS naturally finds all of them: each time the outer loop starts a new exploration from an unvisited vertex, it has found a new component.

Algorithm: ConnectedComponents(G)
  for all v ∈ V: visited(v) = false
  label = 0
  for all v ∈ V:
      if not visited(v):
          label = label + 1
          Explore(v, label)

Algorithm: Explore(v, label)
  comp[v] = label; visited(v) = true
  for each neighbour u of v:
      if not visited(u): Explore(u, label)

Time complexity: $\mathcal{O}(|V| + |E|)$ — DFS touches each vertex and edge once.

Result: comp[v] = comp[u] iff v and u are in the same connected component.

1.2 Checking Connectivity

A graph is connected exactly when label never exceeds 1 — i.e., a single call to Explore from the first vertex already reaches everything.

---

2. Directed Acyclic Graphs (DAGs)

A directed acyclic graph (DAG) is a directed graph with no directed cycles.

Examples of DAGs:

• Task scheduling (task A must complete before task B)
• Prerequisite courses in a curriculum
• Build dependencies in software

2.1 Topological Ordering

A topological ordering of a DAG is a linear ordering of all vertices such that for every edge (u, v), u appears before v in the ordering.

Theorem: A directed graph has a topological ordering $\leftrightarrow$ it is a DAG.

Proof ($\to$): If there were a cycle $v_1 \to v_2 \to \cdots \to v_k \to v_1$, then $v_1$ must come before $v_2$, $v_2$ before $v_3$, …, $v_k$ before $v_1$ — a contradiction.

Algorithm using DFS post-order:

Algorithm: TopologicalSort(G)
  Run DFS on G, recording post times
  Output vertices in decreasing order of post time

Why it works: In a DFS of a DAG, if there is an edge $(u, v)$, then $\text{post}[v] < \text{post}[u]$ ($v$ finishes before $u$, since there are no back edges in a DAG). Reversing post-order gives $u$ before $v$, which is exactly the topological order.

Example: Consider a DAG for course prerequisites:

Calculus → Differential Equations → Numerical Analysis
Calculus → Linear Algebra → Numerical Analysis

Topological order: Calculus, Differential Equations, Linear Algebra, Numerical Analysis (among others).

---

3. Strongly Connected Components (SCCs)

3.1 Definition

In a directed graph, two vertices u and v are in the same strongly connected component if there is a path from u to v and a path from v to u.

The SCCs partition the vertices into maximal subsets that are mutually reachable.

Example:

1 → 2 → 3 → 1    (cycle — all three in one SCC)
3 → 4              (4 is only reachable from 3, not the other way)
4 → 5 → 4         (cycle — {4,5} form an SCC)

SCCs: {1,2,3}, {4,5}

3.2 The Condensation Graph

If we “collapse” each SCC into a single super-vertex and keep the edges between SCCs, we get the condensation (or meta-graph). The condensation is always a DAG (if it had a cycle, those vertices would all belong to the same SCC, contradicting the maximality).

3.3 Kosaraju’s Algorithm

Kosaraju’s algorithm finds all SCCs in two passes of DFS.

Key idea: The vertex with the highest post time in DFS is a “source” SCC (no edges coming in from other SCCs in the condensation). On the reversed graph, this vertex can only reach its own SCC. So the DFS tree rooted at it, in a second pass on $G^R$, gives exactly one SCC. Repeat for the next highest-post vertex, and so on.

Algorithm: SCC(G)
  Run DFS on G; record vertices in decreasing post-time order
  Construct Gᴿ (reverse all edge directions)
  Run DFS on Gᴿ processing vertices in that order
  Each DFS tree in the second pass is one SCC

Time complexity: Two DFS passes $\to$ $\mathcal{O}(|V| + |E|)$.

3.4 Worked Example

Graph: $V = \{1,2,3,4,5\}$, $E = \{(1,2),(2,3),(3,1),(3,4),(4,5),(5,4)\}$. Adjacency list (numeric order): $1:[2]$, $2:[3]$, $3:[1,4]$, $4:[5]$, $5:[4]$.

Pass 1 — DFS on $G$, starting from 1:

Enter 1 (pre=1) → Enter 2 (pre=2) → Enter 3 (pre=3)
  3's neighbours 1 (visited), 4 (unvisited) → Enter 4 (pre=4) → Enter 5 (pre=5)
    5's neighbour 4 already visited → Finish 5 (post=6)
  Finish 4 (post=7)
Finish 3 (post=8)
Finish 2 (post=9)
Finish 1 (post=10)

Post times: $\text{post}(1)=10,\ \text{post}(2)=9,\ \text{post}(3)=8,\ \text{post}(4)=7,\ \text{post}(5)=6$. Decreasing post-time order: $1, 2, 3, 4, 5$.

Pass 2 — build $G^R$ (reverse every edge): $E^R = \{(2,1),(3,2),(1,3),(4,3),(5,4),(4,5)\}$, adjacency list $1:[3]$, $2:[1]$, $3:[2]$, $4:[3,5]$, $5:[4]$. Run DFS on $G^R$, processing vertices in the order found above ($1,2,3,4,5$):

• Start at $1$ (unvisited): $1 \to 3 \to 2$, all now visited. DFS tree $\{1,3,2\}$ $\to$ SCC $\{1,2,3\}$.
• Next in order: $2$ and $3$ already visited, skip. $4$ unvisited: $4 \to 5$, both now visited. DFS tree $\{4,5\}$ $\to$ SCC $\{4,5\}$.
• $5$ already visited, skip. Done.

Result: SCCs $= \{1,2,3\}$ and $\{4,5\}$.

---

4. Breadth-First Search (BFS)

While DFS explores deep first, BFS explores wide first — visiting all neighbours before going deeper.

4.1 Algorithm

Algorithm: BFS(G, s)
  for all u ∈ V: dist(u) = ∞
  dist(s) = 0
  Q = [s]    [queue containing just s]
  while Q is not empty:
      u = eject(Q)
      for all edges (u, v) ∈ E:
          if dist(v) = ∞:
              inject(v, Q)
              dist(v) = dist(u) + 1

4.2 BFS Computes Shortest Paths (by Hop Count)

Theorem: After BFS from source s, dist[v] equals the shortest path distance (in terms of number of edges) from s to v in an unweighted graph.

Proof idea: BFS visits vertices in layers:

• Layer 0: {s}
• Layer 1: all vertices reachable from s in exactly 1 hop
• Layer 2: all vertices reachable in exactly 2 hops, not yet visited
• …

Each vertex v is first reached at distance = shortest hop-count from s. Since BFS respects the layer order (uses a FIFO queue), the first time v is visited gives the shortest path.

4.3 Trace on Example

Graph: A-B, A-C, B-D, C-D, D-E. Start from A.

Queue: [A]
Visit A (dist=0). Neighbours: B, C. Enqueue both.
Queue: [B, C]

Visit B (dist=1). Neighbour D. Enqueue D.
Queue: [C, D]

Visit C (dist=1). Neighbour D. Already enqueued, skip.
Queue: [D]

Visit D (dist=2). Neighbour E. Enqueue E.
Queue: [E]

Visit E (dist=3).
Queue: []

Distances: dist[A]=0, dist[B]=1, dist[C]=1, dist[D]=2, dist[E]=3.

Time complexity: Each vertex and each edge is processed once $\to$ $\mathcal{O}(|V| + |E|)$.

4.4 BFS vs DFS

Property	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO) / recursion
Order of exploration	Level by level (wide)	Deep before wide
Shortest paths (unweighted)	Yes — optimal	No
Cycle detection	Yes	Yes
Space (worst case)	$\mathcal{O}(|V|)$	$\mathcal{O}(|V|)$
Typical use	Shortest paths, connectivity	Topological sort, SCCs

---

5. Weighted Graphs and Shortest Paths

5.1 Weighted Graphs

In many real applications (road networks, communication costs), edges have non-negative weights representing distance, time, or cost.

A weighted graph $G = (V, E, w)$ adds a weight function $w: E \to \mathbb{R}$ (or $\mathbb{R}_{\geq 0}$ for non-negative weights).

Shortest path problem: Given a weighted graph and a source s, find the minimum-weight path from s to every other vertex.

BFS no longer works when edges have different weights. Example: If A-B has weight 10 and A-C-B has weights $1+1=2$, BFS would report $\text{dist}(A,B) = 1$ hop, but the actual shortest path goes through C (total weight $2 < 10$).

5.2 Path Lengths

The length of a path is the sum of edge weights along it. The shortest path from u to v minimises this sum.

Note: If all edge weights are equal (say, all = 1), BFS gives the shortest path. For general weights, we need Dijkstra’s algorithm.

---

6. Dijkstra’s Algorithm

Dijkstra’s algorithm solves the single-source shortest path problem for graphs with non-negative edge weights.

6.1 The Greedy Idea

Maintain a set $S$ of vertices whose shortest distances are finalised. Initially $S = \emptyset$ and $\text{dist}[s] = 0$, $\text{dist}[v] = \infty$ for all $v \neq s$.

At each step:

1. Pick the vertex $u \notin S$ with the smallest current $\text{dist}[u]$.
2. Add $u$ to $S$ (finalise its distance).
3. Update: for each edge $(u, v)$ with weight $l(u,v)$: if $\text{dist}[u] + l(u,v) < \text{dist}[v]$, then $\text{dist}[v] = \text{dist}[u] + l(u,v)$.

Step 3 is called edge relaxation.

Algorithm: Dijkstra(G, l, s)
  for all u ∈ V:
      dist(u) = ∞
      prev(u) = nil
  dist(s) = 0
  H = makequeue(V)    [priority queue keyed by dist values]
  while H is not empty:
      u = deletemin(H)
      for all edges (u, v) ∈ E:
          if dist(u) + l(u, v) < dist(v):
              dist(v) = dist(u) + l(u, v)
              prev(v) = u
              decreasekey(H, v)

6.2 Proof of Correctness

Claim: When a vertex u is extracted from H (i.e., added to S), dist[u] is its true shortest-path distance from s.

Proof by induction:

• Base: The first vertex extracted is $s$, with $\text{dist}[s] = 0$. Correct since $s$ is the source.
• Inductive step: Suppose the claim holds for all previously extracted vertices. When we extract $u$, suppose for contradiction that the true distance $d^*(u) < \text{dist}[u]$. Then there exists a path $s \to \cdots \to x \to y \to \cdots \to u$ where $x \in S$, $y \notin S$, and this path is shorter. But when $x$ was added to $S$, we relaxed $(x, y)$, so $\text{dist}[y] \leq d^*(x) + l(x,y) = d^*(y) \leq d^*(u) < \text{dist}[u]$. So $\text{dist}[y] < \text{dist}[u]$, meaning $y$ would be extracted before $u$ — contradicting that $u$ has the minimum dist in H. $\blacksquare$

Critical requirement: All edge weights must be non-negative (otherwise, a later relaxation could improve the distance of an already-finalised vertex).

6.3 Step-by-Step Trace

Graph: vertices $\{A, B, C, D, E\}$, edges and weights:

A-B: 4, A-C: 2, B-C: 1, B-D: 5, C-D: 8, C-E: 10, D-E: 2

Source: A. Initial: $\text{dist} = \{A:0, B:\infty, C:\infty, D:\infty, E:\infty\}$

Step 1: Extract A (dist=0). Relax A-B: dist[B]=4. Relax A-C: dist[C]=2.
        dist = {A:0, B:4, C:2, D:∞, E:∞}

Step 2: Extract C (dist=2). Relax C-B: dist[B]=min(4, 2+1)=3. 
        Relax C-D: dist[D]=min(∞, 2+8)=10. Relax C-E: dist[E]=min(∞,2+10)=12.
        dist = {A:0, B:3, C:2, D:10, E:12}

Step 3: Extract B (dist=3). Relax B-D: dist[D]=min(10, 3+5)=8.
        dist = {A:0, B:3, C:2, D:8, E:12}

Step 4: Extract D (dist=8). Relax D-E: dist[E]=min(12, 8+2)=10.
        dist = {A:0, B:3, C:2, D:8, E:10}

Step 5: Extract E (dist=10). No outgoing edges to update.

Final shortest distances from A: $B=3, C=2, D=8, E=10$. Shortest path to E: $A \to C \to B \to D \to E$ (total: $2+1+5+2=10$).

---

7. Priority Queue Implementations

Dijkstra’s algorithm’s efficiency depends on the priority queue operations:

• deletemin: remove the vertex with smallest dist — called $|V|$ times
• decreasekey: decrease a key — called at most $|E|$ times

Priority Queue	deletemin	decreasekey	Dijkstra Total
Unsorted array	$\mathcal{O}(|V|)$	$\mathcal{O}(1)$	$\mathcal{O}(|V|^2 + |E|) = \mathcal{O}(|V|^2)$
Binary heap	$\mathcal{O}(\log |V|)$	$\mathcal{O}(\log |V|)$	$\mathcal{O}((|V| + |E|) \log |V|)$
Fibonacci heap	$\mathcal{O}(\log |V|)$ amortised	$\mathcal{O}(1)$ amortised	$\mathcal{O}(|V| \log |V| + |E|)$

• Unsorted array: Simple to implement. Best for dense graphs where $|E| \approx |V|^2$, giving $\mathcal{O}(|V|^2)$.
• Binary heap: Best for sparse graphs ($|E| \ll |V|^2$), giving $\mathcal{O}((|V|+|E|) \log |V|)$.
• Fibonacci heap: Theoretically optimal but complex to implement; mainly used in theory.

In Python: Use heapq module for a binary min-heap implementation.

---

8. Shortest Paths in Directed Acyclic Graphs (DAGs)

For DAGs, we can compute shortest paths in $\mathcal{O}(|V| + |E|)$ — even faster than Dijkstra and without requiring non-negative weights (works for negative weights too, as long as there’s no negative cycle — but DAGs have no cycles at all).

8.1 Algorithm

Algorithm: DAGShortestPath(G, l, s)
  Linearise G (topological sort)
  for all u ∈ V: dist(u) = ∞
  dist(s) = 0
  for each u ∈ V in linearised order:
      for each edge (u, v) ∈ E:
          if dist(u) + l(u, v) < dist(v):
              dist(v) = dist(u) + l(u, v)

Why it works: In a DAG, if we process vertices in topological order, all edges from u go to vertices v that appear later in the topological order. So when we process u, all edges into u have already been considered, meaning dist[u] is already finalised.

8.2 Trace Example

DAG: $A \to B$ (weight 3), $A \to C$ (weight 1), $B \to D$ (weight 2), $C \to B$ (weight 1), $C \to D$ (weight 5)

Topological order: A, C, B, D

dist = {A:0, B:∞, C:∞, D:∞}
Process A: relax A→B: dist[B]=3. relax A→C: dist[C]=1.
Process C: relax C→B: dist[B]=min(3, 1+1)=2. relax C→D: dist[D]=min(∞,1+5)=6.
Process B: relax B→D: dist[D]=min(6, 2+2)=4.
Process D: no outgoing edges.

Final: $A \to C \to B \to D$ with total weight 4. Computed in $\mathcal{O}(|V|+|E|)$ time.

---

9. Summary

Topic	Algorithm	Time Complexity
Connectivity check	DFS	$\mathcal{O}(|V| + |E|)$
Connected components	DFS with labelling	$\mathcal{O}(|V| + |E|)$
Topological sort	DFS post-order (reversed)	$\mathcal{O}(|V| + |E|)$
Strongly connected components	Kosaraju (2 DFS passes)	$\mathcal{O}(|V| + |E|)$
BFS	Level-by-level exploration	$\mathcal{O}(|V| + |E|)$
Shortest paths (unweighted)	BFS	$\mathcal{O}(|V| + |E|)$
Shortest paths (non-negative weights)	Dijkstra + binary heap	$\mathcal{O}((|V|+|E|) \log |V|)$
Shortest paths (DAG, any weights)	DP on topological order	$\mathcal{O}(|V| + |E|)$

---

10. Practice Problems

1. Run BFS from vertex 1 on the graph: $V = \{1,2,3,4,5\}$, $E = \{(1,2),(1,3),(2,4),(3,4),(4,5)\}$. Record the BFS tree and distances.

2. Find all strongly connected components of the directed graph: $V = \{1,2,3,4,5\}$, $E = \{(1,2),(2,3),(3,1),(2,4),(4,5),(5,2)\}$.

3. Give a topological ordering of the following DAG: courses C1, C2, C3, C4, C5 with prerequisites $C1 \to C3$, $C1 \to C4$, $C2 \to C4$, $C3 \to C5$, $C4 \to C5$.

4. Run Dijkstra’s algorithm from vertex S on this graph: S-A: 7, S-B: 3, A-C: 4, B-C: 2, B-A: 1, C-D: 5. Show the state of the distance array after each extraction.

5. Prove that BFS on an unweighted graph always finds shortest paths.

6. Why does Dijkstra’s algorithm fail when some edge weights are negative? Give a counterexample.

7. Find the shortest paths from A in the following DAG using the linear-time DP algorithm: $A \to B: 3$, $A \to C: 6$, $B \to C: 2$, $B \to D: 7$, $C \to D: 1$. Topological order: A, B, C, D.

8. What is the time complexity of Dijkstra’s algorithm with:
   • a) An unsorted array as priority queue
   • b) A binary heap as priority queue Show your working.

9. Can Dijkstra’s algorithm be used on directed graphs? Explain.

10. Challenge: Prove that the condensation of any directed graph is a DAG.

---

← Previous Module Course Home Next Module →