Past exam question: 2062 Baishakh (Regular / Back), Q8
Open in the Padhaiko appQuestion
Write an algorithm of depth first topological sorting. Create spanning tree using depth first traversal method of given graph. Show the steps clearly.
[figure: directed graph on 8 vertices A, B, C, D, E, F, G, H with directed edges A->C, A->D, C->G, G->B, G->F, F->G, B->H, B->E, B->F]
Solution
Depth-First Topological Sorting Algorithm:
Algorithm DFS_TOPOSORT(G = (V, E)):
1. Mark all vertices v in V as unvisited; initialize empty stack S
2. For each vertex v in V:
If !visited[v]: DFS_VISIT(v, S)
3. Pop vertices from S one by one to output the topological ordering
Procedure DFS_VISIT(u, S):
1. visited[u] = TRUE
2. For each neighbor v of u:
If !visited[v]:
DFS_VISIT(v, S)
3. PUSH(S, u) // push after all descendants finishDFS Spanning Tree Construction on the Given Graph (Start from A, Alphabetical Neighbor Order):
- Visit
A(stack[A]). Unvisited neighbors:C, D. Take edgeA -> C. - Visit
C(stack[A, C]). Neighbor:G. Take edgeC -> G. - Visit
G(stack[A, C, G]). Neighbors:B, F. Take edgeG -> B. - Visit
B(stack[A, C, G, B]). Neighbors:E, F, H. Take edgeB -> E. - Visit
E: no outgoing edges backtrack toB. - From
B, next unvisited neighbor isF. Take edgeB -> F. - Visit
F: only neighborGis already visited (F -> Gis a back edge, skipped) backtrack toB. - From
B, next unvisited neighbor isH. Take edgeB -> H. - Visit
H: no outgoing edges backtrackB -> G -> C -> A. - From
A, remaining unvisited neighbor isD. Take edgeA -> D. - Visit
D: no outgoing edges backtrack toA; all 8 vertices visited!
DFS Spanning Tree Edges (7 edges): A->C, C->G, G->B, B->E, B->F, B->H, A->D.
A
/ \
C D
|
G
|
B
/ | \
E F HAnswer:
- DFS Topological Sort: Pushes each vertex onto a stack after visiting all descendants; popping gives a valid topological order.
- DFS Spanning Tree (from
A): RootAwith edgesA->C, C->G, G->B, B->E, B->F, B->H, A->D(all 8 vertices spanned by 7 tree edges).