Directed Acyclic Graphs and Topological Ordering Short Notes for GATE DA

Directed Acyclic Graphs and Topological Ordering short notes for GATE DA: 1 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Exam Readiness: Topological Sort Checklist

Exam Readiness Checklist

Applicability: Only valid for Directed Acyclic Graphs (DAGs).

Kahn's Algorithm: Uses a Queue and in-degrees. Best for cycle detection and counting sorts.

DFS Algorithm: Uses a Stack and post-order traversal. Best for concise recursive implementation.

Complexity: Both methods run in

O (V + E)

time and

O (V)

auxiliary space.

Cycle Check: If the final sorted list length

< V

, a cycle is present.

Multiple Sorts: Arise from independent vertices (no path between them). Verify options by checking every directed edge

u \to v

Directed Acyclic Graphs and Topological Ordering: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming, Data Structures and Algorithms MCQ

In a task scheduling problem modeled as a directed graph, a valid sequence of tasks that respects all prerequisites can be found using topological sorting. This is strictly possible only if the dependency graph is:

A.
A directed acyclic graph (DAG)
B.
A strongly connected graph
C.
A bipartite graph
D.
A complete graph

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct-recall question on the fundamental prerequisite for topological sorting.

Topological sorting is defined as a linear ordering of vertices such that for every directed edge $u \to v$ , $u$ comes before $v$ . If the graph contains a directed cycle, this condition cannot be satisfied because a vertex would need to appear before itself.

Step 1: Recall the definition of topological sorting and its existence condition.

Step 2: The existence of a topological ordering is equivalent to the graph being a Directed Acyclic Graph (DAG).

Step 3: Strongly connected, bipartite, and complete graphs can all contain cycles and thus do not guarantee a topological ordering.

Answer: A directed acyclic graph (DAG).

Question 2 · Programming, Data Structures and Algorithms MCQ

In Kahn's algorithm for topological sorting, a count of processed vertices is maintained. If the algorithm terminates and the count is strictly less than the total number of vertices $V$ , it indicates a structural property of the graph. The number of vertices that were never processed is exactly:

A.
The number of edges $E$
B.
The number of vertices $V$ minus the count
C.
The count of processed vertices
D.
Zero

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct-recall question on the cycle detection mechanism in Kahn's algorithm.

Kahn's algorithm processes vertices by adding them to the output when their in-degree becomes 0. If the graph has a cycle, the vertices in the cycle will never reach in-degree 0 and will not be processed.

Step 1: The total number of vertices is $V$ .

Step 2: The algorithm successfully processes count vertices.

Step 3: The number of unprocessed vertices is simply the total minus the processed: $V - count$ .

Answer: The number of vertices $V$ minus the count.

Question 3 · Programming, Data Structures and Algorithms MCQ

Which of the following is NOT a valid property of every topological ordering of a DAG?

A.
Every vertex of the DAG appears exactly once in the ordering
B.
For every directed edge $u o v$ , vertex $u$ appears before vertex $v$
C.
The first vertex in the ordering has in-degree $0$ in the original graph
D.
The last vertex in the ordering has in-degree $0$ in the original graph

Correct Answer:

Step-by-Step Solution

Key idea: this is a definition-boundary question — check each property against the formal definition of topological sort. Step 1: Recall the definition. A topological ordering is a linear ordering of all vertices such that for every edge

u \to v

u

comes before

v

. Step 2: Evaluate each option. - (A) "Every vertex appears exactly once" — true by definition of a linear ordering of all vertices. - (B) "For every edge

u \to v

u

before

v

" — this is the defining property itself. True. - (C) "First vertex has in-degree

0

" — true. If the first vertex had an incoming edge from some

w

, then

w

would need to appear before it, contradicting it being first. - (D) "Last vertex has in-degree

0

" — false. The last vertex must have out-degree

0

(no edges leaving it, otherwise the target would need to come after it, but it is last). Its in-degree can be anything. Answer: D Common trap: confusing in-degree with out-degree for the last vertex. The first vertex has in-degree

0

; the last vertex has out-degree

0

. Verification: Consider the DAG

A \to B

. The only topological sort is

A, B

. The last vertex

B

has in-degree

1 \neq = 0

, confirming (D) is false.

Question 4 · Programming, Data Structures and Algorithms MCQ

According to the formal definition of topological sort, the first vertex in any valid topological ordering of a directed graph must satisfy a specific condition regarding its in-degree. The maximum possible value of this in-degree is:

A.
0
B.
1
C.
$V - 1$
D.
$V$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct-recall question on the boundary condition of topological sorting.

By definition, for every edge $u \to v$ , $u$ must appear before $v$ . If the first vertex had an in-degree $> 0$ , it would have an incoming edge from some vertex $w$ , meaning $w$ must appear before it. This contradicts it being the first vertex.

Step 1: Recall the definition of topological sort.

Step 2: The first vertex cannot have any predecessors.

Step 3: Therefore, its in-degree must be exactly 0. The maximum possible value is 0.

Answer: 0.

Question 5 · Programming, Data Structures and Algorithms MCQ

In the DFS-based topological sort algorithm, the timing of when a vertex is pushed onto the stack is crucial for correctness. A vertex $u$ is pushed onto the stack:

A.
When it is first visited during the DFS
B.
Before any of its neighbors are visited
C.
After all its reachable descendants have been completely explored
D.
When its in-degree becomes zero

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct-recall question on the DFS-based topological sort procedure.

The DFS method uses post-order traversal. A vertex is pushed onto the stack only after the recursive DFS has finished exploring all of its descendants. This ensures dependencies are placed below the vertex that depends on them.

Step 1: Recall the DFS topological sort algorithm.

Step 2: The algorithm visits neighbors first, then pushes the current vertex.

Step 3: This is post-order traversal.

Answer: After all its reachable descendants have been completely explored.

Question 6 · Programming, Data Structures and Algorithms NAT

Kahn's algorithm is executed on a directed graph with $6$ vertices. The algorithm terminates and the result list contains exactly $4$ vertices. The number of vertices that were never enqueued during the execution is ______.

Correct Answer:

2.00

Step-by-Step Solution

Key idea: this is a cycle-detection-by-count question — vertices not in the result were never enqueued because their in-degree never reached zero.

Step 1: Kahn's algorithm enqueues a vertex only when its in-degree becomes $0$ . Every enqueued vertex is eventually dequeued and added to the result list.

Step 2: The result list has $4$ vertices, meaning exactly $4$ vertices were enqueued and processed.

Step 3: Total vertices $= 6$ . Vertices never enqueued $= 6 - 4 = 2$ .

Answer: 2.00

Common trap: assuming the unprocessed vertices must form a single cycle of length $2$ . They could be in separate cycles or one larger cycle involving already-processed vertices' edges. The count is still $2$ regardless.

Verification: $4$ processed $+ 2$ unprocessed $= 6$ total vertices. Consistent.

Question 7 · Programming, Data Structures and Algorithms MCQ

A topological ordering of a directed graph is a linear arrangement of its vertices such that every directed edge points forward. If a graph has 3 vertices $X, Y, Z$ and directed edges $X \to Y$ and $Y \to Z$ , the total number of valid topological orderings is:

A.
1
B.
2
C.
3
D.
6

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct-application question on the definition of topological ordering.

The edges $X \to Y$ and $Y \to Z$ enforce the strict order $X$ before $Y$ , and $Y$ before $Z$ .

Step 1: Identify the constraints: $X$ must precede $Y$ , and $Y$ must precede $Z$ .

Step 2: The only linear arrangement satisfying both constraints is $X, Y, Z$ .

Step 3: Count the valid orderings. There is exactly 1.

Answer: 1.

Question 8 · Programming, Data Structures and Algorithms MCQ

Consider the Kahn's algorithm trace for a DAG with vertices A, B, C, D and edges A->B, A->C, B->D, C->D.

Assertion (A): Vertex D is enqueued into the queue only after both B and C have been processed.

Reason (R): The initial in-degree of D is 2, and it is reduced by 1 each time a predecessor is processed.

A.
Both A and R are true, and R correctly explains A
B.
Both A and R are true, but R does not explain A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing the mechanics of Kahn's algorithm.

Step 1: Evaluate Assertion (A). Vertex D has incoming edges from B and C. In Kahn's algorithm, a vertex is enqueued only when its in-degree reaches 0. Since D has two predecessors, it will only be enqueued after both B and C are processed and their outgoing edges are removed. Assertion is TRUE.

Step 2: Evaluate Reason (R). The initial in-degree of D is indeed 2 (from B and C). Each time B or C is processed, the in-degree of D decreases by 1. Reason is TRUE.

Step 3: Check the link. The reason (in-degree reduction) is the exact mechanism that causes the assertion (D is enqueued only after both are processed). R correctly explains A.

Answer: Both A and R are true, and R correctly explains A.

Question 9 · Programming, Data Structures and Algorithms MCQ

A DAG has vertices $P$ , $Q$ , $R$ with directed edges $P \to R$ and $Q \to R$ . Match each vertex pair with the nature of its relative order across all valid topological sorts of this DAG.

A.
P,Q: flexible; P,R: fixed; Q,R: fixed
B.
P,Q: fixed; P,R: flexible; Q,R: flexible
C.
P,Q: fixed; P,R: fixed; Q,R: flexible
D.
P,Q: flexible; P,R: flexible; Q,R: fixed

Correct Answer:

Step-by-Step Solution

Key idea: this is a vertex-independence question — two vertices have a flexible relative order if and only if no directed path connects them.

Step 1: List the directed edges: $P \to R$ and $Q \to R$ .

Step 2: Check each pair for a directed path between them.

$P$ and $Q$ : No edge or path connects $P$ to $Q$ or $Q$ to $P$ . They are independent, so their relative order is flexible.
$P$ and $R$ : Edge $P \to R$ exists, so $P$ must come before $R$ . Fixed.
$Q$ and $R$ : Edge $Q \to R$ exists, so $Q$ must come before $R$ . Fixed.

Step 3: The matching is P,Q: flexible; P,R: fixed; Q,R: fixed.

Answer: A

Common trap: misreading edge direction and concluding $R \to P$ instead of $P \to R$ , which would incorrectly mark P,R as flexible.

Verification: The two valid topological sorts are $P, Q, R$ and $Q, P, R$ . In both, $P$ precedes $R$ and $Q$ precedes $R$ , confirming P,R and Q,R are fixed while P,Q swap.

Question 10 · Programming, Data Structures and Algorithms MCQ

Consider a directed acyclic graph with vertices ${A, B, C, D}$ and directed edges $A \to B$ , $B \to C$ , and $A \to D$ .

Match the vertex pairs in Column I with the existence of a directed path between them (Column II).

Column I: (i) $A$ and $C$ , (ii) $B$ and $D$ , (iii) $A$ and $D$

Column II: (P) A directed path exists between them, (Q) No directed path exists between them

A.
(i) $o$ P, (ii) $o$ P, (iii) $o$ Q
B.
(i) $o$ P, (ii) $o$ Q, (iii) $o$ P
C.
(i) $o$ Q, (ii) $o$ Q, (iii) $o$ P
D.
(i) $o$ Q, (ii) $o$ P, (iii) $o$ Q

Correct Answer:

Step-by-Step Solution

Key idea: This is a path existence question, recognisable because it asks whether a directed path connects specific pairs of vertices in a DAG. The rule of independence for topological sorts relies entirely on this: if no directed path exists, the vertices can swap relative order.

Exam route: Quickly trace paths from each source vertex. $A \to B \to C$ means $A$ reaches $C$ . $B$ and $D$ have no connecting edges. $A \to D$ is a direct path.

Learning route:

Step 1: Understand the definition. A directed path is a sequence of directed edges connecting two vertices. It can be a single edge or a chain of multiple edges.

Step 2: Check pair (i) $A$ and $C$ . The edges are $A \to B$ and $B \to C$ . Following the arrows, $A \to B \to C$ forms a directed path. Match: (i) $\to$ P.

Step 3: Check pair (ii) $B$ and $D$ . The edges from $B$ go only to $C$ . The edges to $D$ come only from $A$ . There is no sequence of directed edges connecting $B$ and $D$ in either direction. Match: (ii) $\to$ Q.

Step 4: Check pair (iii) $A$ and $D$ . The edge $A \to D$ is a direct path of length 1. Match: (iii) $\to$ P.

Combined matching: (i) $\to$ P, (ii) $\to$ Q, (iii) $\to$ P.

Answer: B