When a topological order exists — Aptitude Question
When a topological order exists: A directed graph has a topological ordering exactly when the graph... Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Easy
- Time target: 60 seconds
Question
A directed graph has a topological ordering exactly when the graph...
Options
- contains no directed cycle
- is complete
- is connected
- is strongly connected
Show the answer and the worked solution
Correct answer: A. contains no directed cycle
Worked solution
- A topological order places each vertex before every vertex it points to.
- If there were a directed cycle, each of its vertices would have to precede the next and so, going round, precede itself — impossible.
- Conversely, an acyclic directed graph always has a vertex with no incoming edge; removing it repeatedly produces a valid order.
- Connectivity is irrelevant, since a graph in several pieces can still be ordered. So a topological order exists exactly when the graph contains no directed cycle.
Answer: contains no directed cycle.
The idea
Topological sorting and cycle detection are the same computation: Kahn's algorithm outputs an order, and any vertices it cannot output lie on a cycle.
Shortcut. A topological order exists exactly for DAGs: a directed cycle would force a vertex to come before itself, and connectivity plays no part.
Common trap. "is strongly connected" sounds rigorous, but a strongly connected graph with two or more vertices always contains a cycle, so it rules an order out.
All Data Structures & Algorithms questions · placement mock tests