Exercises — Graph Algorithms
Chapter 8 · Fully solved exercises on BFS, DFS, topological sort, and graph complexity
Exercise 1: BFS Trace
Problem. Run BFS from node \(s\) on the following undirected graph:
- Nodes: \(s, a, b, c, d, e\)
- Edges: \(s\)–\(a\), \(s\)–\(b\), \(a\)–\(c\), \(a\)–\(d\), \(b\)–\(d\), \(c\)–\(e\), \(d\)–\(e\)
Answer: (a) BFS visit order starting from \(s\). (b) BFS layers. (c) Shortest hop-count distances from \(s\).
Solution
We maintain a FIFO queue and a visited set.
| Step | Queue (before pop) | Pop | New neighbors added |
|---|---|---|---|
| 0 | \([s]\) | \(s\) | \(a, b\) |
| 1 | \([a, b]\) | \(a\) | \(c, d\) |
| 2 | \([b, c, d]\) | \(b\) | — (\(s\) visited, \(d\) visited) |
| 3 | \([c, d]\) | \(c\) | \(e\) |
| 4 | \([d, e]\) | \(d\) | — (\(a, b, e\) visited) |
| 5 | \([e]\) | \(e\) | — (\(c, d\) visited) |
BFS order: \(s,\ a,\ b,\ c,\ d,\ e\)
BFS layers:
| Layer | Nodes |
|---|---|
| 0 | \(s\) |
| 1 | \(a,\ b\) |
| 2 | \(c,\ d\) |
| 3 | \(e\) |
Shortest distances from \(s\):
| Node | \(d\) |
|---|---|
| \(s\) | 0 |
| \(a\) | 1 |
| \(b\) | 1 |
| \(c\) | 2 |
| \(d\) | 2 |
| \(e\) | 3 |
BFS tree edges (edges used to discover each node): \(s\)–\(a\), \(s\)–\(b\), \(a\)–\(c\), \(a\)–\(d\), \(c\)–\(e\).
Exercise 2: DFS on a Directed Graph
Problem. Run DFS from node \(s\) on the directed graph:
- Nodes: \(s, a, b, c, d\)
- Arcs: \(s \to a\), \(s \to b\), \(a \to c\), \(b \to c\), \(b \to d\), \(c \to d\)
Adjacency lists are explored in alphabetical order. Record discovery/finish times and classify each edge.
Solution
DFS timestamps (disc / fin):
| Call stack event | Node | disc | fin |
|---|---|---|---|
| visit \(s\) | \(s\) | 1 | 10 |
| → visit \(a\) | \(a\) | 2 | 7 |
| → visit \(c\) | \(c\) | 3 | 6 |
| → visit \(d\) | \(d\) | 4 | 5 |
| → visit \(b\) | \(b\) | 8 | 9 |
Summary:
| Node | disc | fin |
|---|---|---|
| \(s\) | 1 | 10 |
| \(a\) | 2 | 7 |
| \(b\) | 8 | 9 |
| \(c\) | 3 | 6 |
| \(d\) | 4 | 5 |
Edge classification:
| Arc | Type |
|---|---|
| \(s \to a\) | Tree |
| \(a \to c\) | Tree |
| \(c \to d\) | Tree |
| \(s \to b\) | Tree |
| \(b \to c\) | Cross/Forward (disc[\(c\)] < disc[\(b\)], and \(c\) already finished) |
| \(b \to d\) | Cross/Forward (\(d\) already finished) |
Topological order (finish time descending): \(s,\ b,\ a,\ c,\ d\)
Exercise 3: Topological Sort
Problem. Find all valid topological orderings of the DAG:
- Nodes: \(A, B, C, D, E, F\)
- Arcs: \(A \to C\), \(A \to D\), \(B \to D\), \(B \to E\), \(C \to F\), \(D \to F\), \(E \to F\)
How many valid orderings exist? List at least three.
Solution
In-degrees:
| Node | In-degree | Sources |
|---|---|---|
| \(A\) | 0 | — |
| \(B\) | 0 | — |
| \(C\) | 1 | \(A\) |
| \(D\) | 2 | \(A, B\) |
| \(E\) | 1 | \(B\) |
| \(F\) | 3 | \(C, D, E\) |
Kahn’s algorithm starts with in-degree-0 nodes \(\{A, B\}\). At each step any node with current in-degree 0 may be chosen, giving multiple valid orderings.
Constraints: \(A\) before \(C, D\); \(B\) before \(D, E\); \(C, D, E\) all before \(F\).
Valid orderings (6 examples):
| # | Ordering |
|---|---|
| 1 | \(A, B, C, D, E, F\) |
| 2 | \(A, B, C, E, D, F\) |
| 3 | \(A, B, E, C, D, F\) |
| 4 | \(A, B, E, D, C, F\) |
| 5 | \(B, A, C, D, E, F\) |
| 6 | \(B, A, D, E, C, F\) |
The total count equals the number of linear extensions of the partial order; computing it exactly requires DP but is at least 12.
Exercise 4: Complexity on Special Graph Classes
Problem. For each problem below, state whether it is polynomial (P) or NP-hard on (i) general graphs, (ii) trees, (iii) bipartite graphs, (iv) DAGs. Briefly justify.
- Maximum independent set
- Shortest path between two nodes (non-negative weights)
- Hamiltonian path (visit all nodes exactly once)
- Graph colouring (find the chromatic number)
Solution
| General | Trees | Bipartite | DAGs | |
|---|---|---|---|---|
| 1. Max independent set | NP-hard | P | P | NP-hard |
| 2. Shortest path | P | P | P | P |
| 3. Hamiltonian path | NP-hard | P | NP-hard | P |
| 4. Graph colouring | NP-hard | P | P | NP-hard |
Notes:
- Max independent set — Trees: By König’s theorem, max independent set = \(n -\) max matching; max matching on trees is solvable by DP in \(O(n)\).
- Max independent set — Bipartite: By König’s theorem, max independent set = \(n -\) max matching = \(n -\) min vertex cover; max matching in bipartite graphs is polynomial (Hopcroft-Karp).
- Shortest path: Dijkstra (\(O((n+m)\log n)\)) works on all four classes. On DAGs it can be done in \(O(n+m)\) by relaxing edges in topological order.
- Hamiltonian path — Trees: A tree has a Hamiltonian path if and only if it is itself a path (i.e., every vertex has degree ≤ 2). Check in \(O(n)\).
- Hamiltonian path — Bipartite: Still NP-hard in general bipartite graphs.
- Hamiltonian path — DAGs: DP on topological order: check whether there is a path covering all nodes. Solvable in \(O(n+m)\).
- Graph colouring — Trees: Trees are 1-colourable if they have no edges, 2-colourable otherwise (they are bipartite). \(O(n)\).
- Graph colouring — Bipartite: Always 2-colourable; verify with BFS in \(O(n+m)\).
Exercise 5: Connected Components and DFS
Problem. An undirected graph has nodes \(\{1,2,3,4,5,6,7\}\) and edges \(\{1\text{–}2,\ 1\text{–}3,\ 2\text{–}3,\ 4\text{–}5,\ 6\text{–}7\}\).
- How many connected components? Name them.
- Run DFS from node 1. Which nodes are visited?
- What is the minimum number of edges needed to make the graph connected?
Solution
(a) Connected components.
Inspecting adjacency:
- Nodes \(1, 2, 3\) are mutually connected → component \(C_1 = \{1,2,3\}\)
- Nodes \(4, 5\) are connected → component \(C_2 = \{4,5\}\)
- Nodes \(6, 7\) are connected → component \(C_3 = \{6,7\}\)
There are 3 connected components.
(b) DFS from node 1.
DFS explores the component of the starting node. Starting from 1 (adjacency order: 2 then 3):
- Visit 1 → visit 2 → visit 3 (3’s neighbors 1,2 already visited) → backtrack → backtrack
Visited: \(\{1, 2, 3\}\). Nodes \(4, 5, 6, 7\) are not reachable from 1.
DFS tree edges: \(1 \to 2\), \(2 \to 3\). Back edge: \(3 \to 1\) (or \(3 \to 2\) depending on order).
(c) Minimum edges to connect.
To merge \(k\) connected components into one we need at least \(k - 1\) edges. Here \(k = 3\), so we need 2 edges.
Example: add edge \(3\)–\(4\) (merges \(C_1\) and \(C_2\)) and edge \(5\)–\(6\) (merges the result with \(C_3\)).