Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

Question

For this I came up with a DFS recursion.

Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing.

The element with the highest post number or the last element you visit should be the first element in your topological ordering.

Now do another DFS recursion that executes on every node called DFS_find:

DFS_find(Node):
    if (node has no neighbors):
        return 1;
    otherwise: 
        return 1 + the maximum of DFS_find(Node) for all neighboring nodes

Execute DFS_find(Node) on the first node in your topological ordering. If it returns a number equal to the number of vertices, then a directed path that crosses every node once, exists. Otherwise it does not.

How can I prove whether or not this algorithm is correct?

I think this may be a little less time efficient than the classical way to just do a topological sort and then check if each consecutive pair has an edge between them.

Answer 1

Assume the graph is a directed acyclic graph throughout.

The algorithm is correct

In the first recursion, the algorithm finds a node $u$ that has no incoming edges.

In the second recursion, the algorithm checks whether $p(u)=n$, where for each node $v$, $p(v)$ is 1 plus the length of the longest path starting from that node.

There is a path that reaches all nodes if and only if $p(v)=n$ for some node $v$. Since the graph is acyclic, a path cannot revisit any node. Since the graph is acyclic, if $p(v)=n$ for some node $v$, that node must be the unique node that have no incoming edges. Hence, there is path that reaches all nodes without revisiting a node if and only if $p(v)=n$ for some node that has no incoming edges.

Combining the three paragraphs above, we see that the algorithm is correct.

Two easy exercises

1. Show that DFS_find(Node) returns $p(\text{Node})$.
2. Show that there is a path that reaches all nodes if and only if $p(v)=n$ for some node $v$.