Given below are two statements: one is labelled as Assertion A and the other…
2026
Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.
Assertion A: Depth first search can be used to perform a topological sort of a directed acyclic graph.
Reason R: A topological sort of a directed acyclic graph G = (V, E) is a linear ordering of its vertices such that if G contains an edge (u, v) then u appears before v in the ordering.
In the light of the above statements, choose the most appropriate answer from the options given below:
- A.
Both A and R are correct and R is the correct explanation of A
- B.
Both A and R are correct but R is NOT the correct explanation of A
- C.
A is correct but R is not correct
- D.
A is not correct but R is correct
Attempted by 201 students.
Show answer & explanation
Correct answer: B
Assertion A is correct because Depth First Search (DFS) can be used to perform a topological sort on a Directed Acyclic Graph (DAG). The algorithm works by recording vertices in reverse order of their completion times.
Reason R is also correct as it accurately defines a topological sort: a linear ordering where for every directed edge (u, v), vertex u comes before v in the ordering.
However, Reason R merely states the definition of the result and does not explain the algorithmic mechanism (DFS traversal and finish times) that makes Assertion A true. Therefore, while both statements are individually true, R is not the correct explanation for A.
Thus, the correct choice is Option 1.