Module III — Graph 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 Using DFS to Check Connectivity

Run DFS from any vertex v. If all vertices are visited, the graph is connected.

Algorithm: IsConnected(G)
  run DFS from vertex 1
  if all vertices are marked visited: return True
  else: return False

1.2 Connected Components

If the graph is not connected, it has multiple connected components — maximal subgraphs that are connected within themselves.

DFS naturally finds all components: each time we start DFS from an unvisited vertex, we discover a new component.

Algorithm: FindComponents(G)
  comp[] = array of -1 (unassigned)
  k = 0                          [component counter]
  for each vertex v ∈ V:
      if comp[v] = -1:
          DFS-and-label(G, v, k)
          k++

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

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
  output vertices in reverse order of their post-visit numbers

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 belongs to a “source SCC” (one with no incoming edges in the condensation). If we run DFS on the reversed graph $G^R$ (all edges flipped), the vertex with the highest post-time belongs to a “sink SCC” — and DFS from it in the original graph $G$ explores exactly that SCC.

Algorithm: Kosaraju(G)
  Step 1: Run DFS on Gᴿ (reversed graph). Record post-visit times.
  Step 2: Run DFS on G, processing vertices in decreasing post-time order.
          Each DFS tree from Step 2 is one SCC.

3.4 Worked Example

Graph: $V = {1,2,3,4,5}$, $E = {(1,2),(2,3),(3,1),(3,4),(4,5),(5,4)}$

Reversed graph $G^R$: $E = {(2,1),(3,2),(1,3),(4,3),(5,4),(4,5)}$

Step 1 — DFS on $G^R$ (starting from 1): Let’s say we get post-order: $3, 2, 1, \ldots, 5, 4$ (reversed: $\text{post}(1) > \text{post}(2) > \text{post}(3)$). After DFS on $G^R$ starting from 1: post times (say) — $4 \to 5 \to 5$ finishes, 4 finishes, $3 \to 2 \to 1 \to \cdots$ (working out the full DFS trace on this small example shows SCCs ${1,2,3}$ and ${4,5}$.)

Step 2 — Process in decreasing post-time order in original G:

• First vertex (highest post): some vertex in ${1,2,3}$. DFS explores ${1,2,3}$ $\to$ SCC 1.
• Next unvisited: vertex 4 (or 5). DFS explores ${4,5}$ $\to$ SCC 2.

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)    [s = source vertex]
  for each vertex v: dist[v] = ∞, visited[v] = False
  dist[s] = 0
  queue Q = {s}
  visited[s] = True
  while Q is not empty:
      v = dequeue(Q)
      for each neighbour u of v:
          if not visited[u]:
              visited[u] = True
              dist[u] = dist[v] + 1
              enqueue(Q, u)

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.

4.4 BFS vs DFS

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 $w(u,v)$: if $\text{dist}[u] + w(u,v) < \text{dist}[v]$, then $\text{dist}[v] = \text{dist}[u] + w(u,v)$.

Step 3 is called edge relaxation.

Algorithm: Dijkstra(G, s)
  for each vertex v: dist[v] = ∞, prev[v] = null
  dist[s] = 0
  S = {}                         [set of finalised vertices]
  PQ = priority queue of all vertices, keyed by dist[]
  while PQ is not empty:
      u = ExtractMin(PQ)         [vertex with smallest dist[u]]
      S = S ∪ {u}
      for each edge (u, v) ∈ E:
          if dist[u] + w(u,v) < dist[v]:
              dist[v] = dist[u] + w(u,v)
              prev[v] = u
              UpdateKey(PQ, v, dist[v])

6.2 Proof of Correctness

Claim: When a vertex u is extracted from PQ (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) + w(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 PQ. $\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:

• ExtractMin: remove the vertex with smallest dist — called $

  V

  $ times

• UpdateKey: decrease a key — called at most $

  E

  $ times

• Unsorted array: Simple to implement. Best for dense graphs where $E \approx V^2$, giving $O(V^2)$.
• Binary heap: Best for sparse graphs ($E \ll V^2$), giving $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)

8.1 Algorithm

Algorithm: DAGShortestPath(G, s)
  for each vertex v: dist[v] = ∞
  dist[s] = 0
  process vertices in topological order:
      for each vertex u (in topological order):
          for each edge (u, v) ∈ E:
              if dist[u] + w(u,v) < dist[v]:
                  dist[v] = dist[u] + w(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 $O(V+E)$ time.

9. Summary

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.