Algorithm for finding a Hamiltonian Path in a DAG

You can first topologically sort the DAG (every DAG can be topologically sorted) in O(n+m).

Once this is done, you know that edge go from lower index vertices to higher.
This means that there exists a Hamiltonian path if and only if there are edge between consecutive vertices, e.g.

(1,2), (2,3), ..., (n-1,n).

(This is because in a Hamiltonian path you can’t “go back” and yet you have to visit all, so the only way is to “not skip”)

You can check this condition in O(n).

Thus, the overall complexity is O(m+n).

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)