Past exam question: 2079 Ashwin (Back), Q11(a)
Open in the Padhaiko appDetermine the breadth first topological sorting for the following graph.
(1) ---------> (2)
/ | \ / \
/ | \ / \
v | v v v
(3) | (4) <--- (5)
\ | / \ /
\ | / \ /
v v v v v
(6) <----- (7) <--
Directed Edges: ; ; ; ; ; .
Solution
Breadth-First Topological Sorting Principles (Kahn's Algorithm): Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge , vertex appears before vertex .
Kahn's Algorithm (BFS-based):
- Compute the in-degree (number of incoming directed edges) for each vertex .
- Initialize a FIFO Queue with all vertices having an in-degree of (independent source vertices).
- While the queue is not empty:
- Dequeue a vertex and append it to the topological ordering.
- For every adjacent vertex (edge ), decrement by 1.
- If becomes , enqueue vertex .
- If the number of processed vertices equals , a valid topological sort is found.
Initial In-Degree Computation: Total vertices .
| Vertex () | Incoming Edges | Initial In-Degree |
|---|---|---|
| 1 | None (source node) | 0 |
| 2 | 1 | |
| 3 | 2 | |
| 4 | 3 | |
| 5 | 1 | |
| 6 | 3 | |
| 7 | 2 |
Initial Queue (only vertex 1 has in-degree 0).
Step-by-Step Execution of Kahn's Algorithm:
- Iteration 1:
- Dequeue vertex 1. Output:
[1]. - Remove outgoing edges from 1:
- Enqueue 2.
- .
- .
- Queue: .
- Dequeue vertex 1. Output:
- Iteration 2:
- Dequeue vertex 2. Output:
[1, 2]. - Remove outgoing edges from 2:
- Enqueue 5.
- .
- Queue: .
- Dequeue vertex 2. Output:
- Iteration 3:
- Dequeue vertex 5. Output:
[1, 2, 5]. - Remove outgoing edges from 5:
- Enqueue 4.
- .
- Queue: .
- Dequeue vertex 5. Output:
- Iteration 4:
- Dequeue vertex 4. Output:
[1, 2, 5, 4]. - Remove outgoing edges from 4:
- Enqueue 3.
- Enqueue 7.
- .
- Queue: .
- Dequeue vertex 4. Output:
- Iteration 5:
- Dequeue vertex 3. Output:
[1, 2, 5, 4, 3]. - Remove outgoing edge from 3:
- .
- Queue: .
- Dequeue vertex 3. Output:
- Iteration 6:
- Dequeue vertex 7. Output:
[1, 2, 5, 4, 3, 7]. - Remove outgoing edge from 7:
- Enqueue 6.
- Queue: .
- Dequeue vertex 7. Output:
- Iteration 7:
- Dequeue vertex 6. Output:
[1, 2, 5, 4, 3, 7, 6]. - Vertex 6 has no outgoing edges.
- Queue is now empty ().
- Dequeue vertex 6. Output:
Dependency Verification: Checking every edge against the generated order 1, 2, 5, 4, 3, 7, 6:
- : 1 appears before 2, 3, and 4 (Satisfied).
- : 2 appears before 4 and 5 (Satisfied).
- : 5 appears before 4 and 7 (Satisfied).
- : 4 appears before 3, 6, and 7 (Satisfied).
- : 3 appears before 6 (Satisfied).
- : 7 appears before 6 (Satisfied).
All 12 edge dependencies are strictly satisfied.
The breadth-first (Kahn's algorithm) topological sort sequence for the graph is:
(or if tie-breaking selects 7 before 3 in the queue).