Past exam question: 2079 Ashwin (Back), Q11(b)
Open in the Padhaiko appDetermine the depth 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
Depth-First Search (DFS) Topological Sort Methodology: In a Directed Acyclic Graph (DAG), depth-first topological sorting relies on the post-order (finishing times) of DFS:
- Maintain vertex state:
UNVISITED,VISITING(currently in recursion call stack), andFINISHED. - Initialize an empty LIFO stack (or reverse-order list).
- For each unvisited vertex , invoke recursive
DFS(u):- Mark as
VISITING. - For each adjacent neighbor of :
- If is
UNVISITED, recursively callDFS(v). - (If is
VISITING, a back-edge exists, indicating a cycle; in a valid DAG this cannot occur).
- If is
- Mark as
FINISHED. - Push vertex onto the output stack.
- Mark as
- When all vertices are processed, popping the stack completely yields the topological sort (reverse post-order).
Recursive DFS Traversal Trace: We initiate DFS from the unique source vertex 1 (tie-breaking neighbor visits by ascending numerical order):
- Call
DFS(1): Mark 1 asVISITING.- Inspect neighbors of 1:
[2, 3, 4]. - First unvisited neighbor is 2 Call
DFS(2).
- Inspect neighbors of 1:
- Call
DFS(2): Mark 2 asVISITING.- Inspect neighbors of 2:
[4, 5]. - First unvisited neighbor is 4 Call
DFS(4).
- Inspect neighbors of 2:
- Call
DFS(4): Mark 4 asVISITING.- Inspect neighbors of 4:
[3, 6, 7]. - First unvisited neighbor is 3 Call
DFS(3).
- Inspect neighbors of 4:
- Call
DFS(3): Mark 3 asVISITING.- Inspect neighbor of 3:
[6]. - Unvisited neighbor is 6 Call
DFS(6).
- Inspect neighbor of 3:
- Call
DFS(6): Mark 6 asVISITING.- Vertex 6 has no outgoing edges (sink node).
- Mark 6 as
FINISHED. - Push 6 onto Stack. Stack:
[6]. Return toDFS(3).
- Resume
DFS(3):- All neighbors explored. Mark 3 as
FINISHED. - Push 3 onto Stack. Stack:
[6, 3]. Return toDFS(4).
- All neighbors explored. Mark 3 as
Completing Exploration from Vertex 4:
- Resume
DFS(4):- Next neighbor of 4 is 6 (already
FINISHED). - Next unvisited neighbor is 7 Call
DFS(7).
- Next neighbor of 4 is 6 (already
- Call
DFS(7): Mark 7 asVISITING.- Inspect neighbor of 7:
[6]. Vertex 6 is alreadyFINISHED. - Mark 7 as
FINISHED. - Push 7 onto Stack. Stack:
[6, 3, 7]. Return toDFS(4).
- Inspect neighbor of 7:
- Resume
DFS(4):- All neighbors of 4 explored. Mark 4 as
FINISHED. - Push 4 onto Stack. Stack:
[6, 3, 7, 4]. Return toDFS(2).
- All neighbors of 4 explored. Mark 4 as
Exploring Vertex 5 and Finishing 2 and 1:
- Resume
DFS(2):- Next unvisited neighbor of 2 is 5 Call
DFS(5).
- Next unvisited neighbor of 2 is 5 Call
- Call
DFS(5): Mark 5 asVISITING.- Neighbors of 5 are
[4, 7]. Both 4 and 7 are alreadyFINISHED. - Mark 5 as
FINISHED. - Push 5 onto Stack. Stack:
[6, 3, 7, 4, 5]. Return toDFS(2).
- Neighbors of 5 are
- Resume
DFS(2):- All neighbors explored. Mark 2 as
FINISHED. - Push 2 onto Stack. Stack:
[6, 3, 7, 4, 5, 2]. Return toDFS(1).
- All neighbors explored. Mark 2 as
- Resume
DFS(1):- Next neighbors of 1 are 3 and 4 (both already
FINISHED). - Mark 1 as
FINISHED. - Push 1 onto Stack. Stack:
[6, 3, 7, 4, 5, 2, 1].
- Next neighbors of 1 are 3 and 4 (both already
Final Stack Pop Sequence (Topological Order): Popping elements one by one from the stack (from top to bottom):
Validation of Dependencies:
- : 1 precedes 2, 3, 4.
- : 2 precedes 4, 5.
- : 5 precedes 4, 7.
- : 4 precedes 3, 6, 7.
- : 7 precedes 6.
- : 3 precedes 6.
Every directed edge points strictly from left to right.
The depth-first search (DFS reverse post-order) topological sorting for the graph is:
(or depending on whether neighbor 3 or 7 is explored first).