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.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is