PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q11(b)

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Graphs

Question

Determine 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:

  1. Maintain vertex state: UNVISITED, VISITING (currently in recursion call stack), and FINISHED.
  2. Initialize an empty LIFO stack (or reverse-order list).
  3. For each unvisited vertex , invoke recursive DFS(u):
    • Mark as VISITING.
    • For each adjacent neighbor of :
      • If is UNVISITED, recursively call DFS(v).
      • (If is VISITING, a back-edge exists, indicating a cycle; in a valid DAG this cannot occur).
    • Mark as FINISHED.
    • Push vertex onto the output stack.
  4. 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):

  1. Call DFS(1): Mark 1 as VISITING.
    • Inspect neighbors of 1: [2, 3, 4].
    • First unvisited neighbor is 2 Call DFS(2).
  2. Call DFS(2): Mark 2 as VISITING.
    • Inspect neighbors of 2: [4, 5].
    • First unvisited neighbor is 4 Call DFS(4).
  3. Call DFS(4): Mark 4 as VISITING.
    • Inspect neighbors of 4: [3, 6, 7].
    • First unvisited neighbor is 3 Call DFS(3).
  4. Call DFS(3): Mark 3 as VISITING.
    • Inspect neighbor of 3: [6].
    • Unvisited neighbor is 6 Call DFS(6).
  5. Call DFS(6): Mark 6 as VISITING.
    • Vertex 6 has no outgoing edges (sink node).
    • Mark 6 as FINISHED.
    • Push 6 onto Stack. Stack: [6]. Return to DFS(3).
  6. Resume DFS(3):
    • All neighbors explored. Mark 3 as FINISHED.
    • Push 3 onto Stack. Stack: [6, 3]. Return to DFS(4).

Completing Exploration from Vertex 4:

  1. Resume DFS(4):
    • Next neighbor of 4 is 6 (already FINISHED).
    • Next unvisited neighbor is 7 Call DFS(7).
  2. Call DFS(7): Mark 7 as VISITING.
    • Inspect neighbor of 7: [6]. Vertex 6 is already FINISHED.
    • Mark 7 as FINISHED.
    • Push 7 onto Stack. Stack: [6, 3, 7]. Return to DFS(4).
  3. Resume DFS(4):
    • All neighbors of 4 explored. Mark 4 as FINISHED.
    • Push 4 onto Stack. Stack: [6, 3, 7, 4]. Return to DFS(2).

Exploring Vertex 5 and Finishing 2 and 1:

  1. Resume DFS(2):
    • Next unvisited neighbor of 2 is 5 Call DFS(5).
  2. Call DFS(5): Mark 5 as VISITING.
    • Neighbors of 5 are [4, 7]. Both 4 and 7 are already FINISHED.
    • Mark 5 as FINISHED.
    • Push 5 onto Stack. Stack: [6, 3, 7, 4, 5]. Return to DFS(2).
  3. Resume DFS(2):
    • All neighbors explored. Mark 2 as FINISHED.
    • Push 2 onto Stack. Stack: [6, 3, 7, 4, 5, 2]. Return to DFS(1).
  4. 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].

Final Stack Pop Sequence (Topological Order): Popping elements one by one from the stack (from top to bottom):

Validation of Dependencies:

Every directed edge points strictly from left to right.

Answer:

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).

All past exam questions for Data Structure and Algorithms