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.

• Antti Röyskö: "A little less"? Your algorithm has runtime $\mathcal{O}(2^{n})$ in a complete graph, unless you memoize the values DFS_find(Node), in which case the complexity of both algorithms is linear.
• Joshua Anderson: Yes, I am saying its O(n) because I don't recalculate the values If its a node that I already visited. It is not 2^n...
• Yuval Filmus: I don't understand your problem. If your graph isn't a directed path, there is no directed path that visits all vertices.
• Joshua Anderson: Look at the title. I am only considering DAGS. No cycles, and only directed links.
• 喜欢算法和数学: @MiteshKumar Is my answer helpful? Do you need more details? (This comment will be deleted.)

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$.