Original Question: Algorithm for finding a Hamiltonian Path in a DAG
Chosen Answer:
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).
- Petar Ivanov
How can you check this condition? I don't have enough reputation, hence, I am 'duplicating' the post. Also, no other post that I can find explains how there is access to an edge in constant time.
Given that there are the pairs (1,2),(2,3), ..., (n-1,n) derived from the topological sorting, as a result there will be n-1 pairs of the source vertex and tail vertex (i.e. edges) that will need to be checked. Hence, we will need to iterate over n-1 of these pairs and check if there exists an edge between these two pairs.
So if the condition can be checked 'in O(n)' as stated by Petar, this would conclude that we can access the edges in O(1) (i.e. constant time). There is no mention of an adjacency matrix used or available that would allow us to check if there is an edge between the source vertex and tail vertex in constant time. What am I missing? Is there some sort of data structure used to implement this constant time search in the worst case scenario?