AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Easygraphtopological sort

~60s

When a topological order exists

A directed graph has a topological ordering exactly when the graph...

Show the answer and the worked solution

Correct answer: A.

contains no directed cycle

Worked solution

  1. A topological order places each vertex before every vertex it points to.
  2. If there were a directed cycle, each of its vertices would have to precede the next and so, going round, precede itself — impossible.
  3. Conversely, an acyclic directed graph always has a vertex with no incoming edge; removing it repeatedly produces a valid order.
  4. 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.

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.

Question

A directed graph has a topological ordering exactly when the graph...

Options

  1. contains no directed cycle
  2. is complete
  3. is connected
  4. is strongly connected
Show the answer and the worked solution

Correct answer: A. contains no directed cycle

Worked solution

  1. A topological order places each vertex before every vertex it points to.
  2. If there were a directed cycle, each of its vertices would have to precede the next and so, going round, precede itself — impossible.
  3. Conversely, an acyclic directed graph always has a vertex with no incoming edge; removing it repeatedly produces a valid order.
  4. 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