Skip to interview prep
Apexed

236. How can you decide whether a DAG has a Hamiltonian path in linear time?

MediumGraph algorithms

Technical
Show model answer

Compute a topological order. A Hamiltonian path in a DAG must visit vertices in a topological order, and if it exists that order is forced. So the DAG has a Hamiltonian path iff every pair of consecutive vertices in the topological order is joined by an edge.

That check costs O(V + E). It is the same condition as the topological order being unique. In general graphs, by contrast, the Hamiltonian path problem is NP-complete.

How can you decide whether a DAG has a Hamiltonian path in linear time — Data structures & algorithms interview question — Apexed