Start learning →

Topological sort is well-defined for

Aany undirected graph
Bany directed graph
Cdirected acyclic graphs (DAGs) only
Dgraphs with at least one negative edge weight
Answer & Solution
Correct answer: C. directed acyclic graphs (DAGs) only
Topological sort requires that all edges go forward in the ordering. A cycle would force each of its vertices to precede the others — impossible. So topological sort applies only to directed acyclic graphs. Both DFS-based and Kahn's algorithm detect cycles when they appear: DFS finds a back edge, Kahn's queue empties early.
Practise this question with Quill — GATE CSE →

Keep practising Algorithms

Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.

Start a Algorithms lesson →
Related questions