PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Graphs

Question

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 finish

DFS Spanning Tree Construction on the Given Graph (Start from A, Alphabetical Neighbor Order):

  1. Visit A (stack [A]). Unvisited neighbors: C, D. Take edge A -> C.
  2. Visit C (stack [A, C]). Neighbor: G. Take edge C -> G.
  3. Visit G (stack [A, C, G]). Neighbors: B, F. Take edge G -> B.
  4. Visit B (stack [A, C, G, B]). Neighbors: E, F, H. Take edge B -> E.
  5. Visit E: no outgoing edges backtrack to B.
  6. From B, next unvisited neighbor is F. Take edge B -> F.
  7. Visit F: only neighbor G is already visited (F -> G is a back edge, skipped) backtrack to B.
  8. From B, next unvisited neighbor is H. Take edge B -> H.
  9. Visit H: no outgoing edges backtrack B -> G -> C -> A.
  10. From A, remaining unvisited neighbor is D. Take edge A -> D.
  11. Visit D: no outgoing edges backtrack to A; 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  H
Answer:

All past exam questions for Data Structure and Algorithms