PadhaikoAll subjects

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

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Graphs

Question

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

  1. Compute the in-degree (number of incoming directed edges) for each vertex .
  2. Initialize a FIFO Queue with all vertices having an in-degree of (independent source vertices).
  3. 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 .
  4. If the number of processed vertices equals , a valid topological sort is found.

Initial In-Degree Computation: Total vertices .

Vertex ()Incoming EdgesInitial In-Degree
1None (source node)0
21
32
43
51
63
72

Initial Queue (only vertex 1 has in-degree 0).

Step-by-Step Execution of Kahn's Algorithm:

Dependency Verification: Checking every edge against the generated order 1, 2, 5, 4, 3, 7, 6:

All 12 edge dependencies are strictly satisfied.

Answer:

The breadth-first (Kahn's algorithm) topological sort sequence for the graph is:

(or if tie-breaking selects 7 before 3 in the queue).

All past exam questions for Data Structure and Algorithms