3
$\begingroup$
Given a directed acyclic graph G, give a linear time algorithm to determine if the
graph has a directed path that visits every vertex.

You can assume you are given a list of nodes and two adjacency lists: Enter[v] which contains all the edges entering node v, and Exit[v] which contains all the edges leaving node v.

I was thinking that I could pick a node that doesn't have edges entering it and run DFS on it. During DFS, every time I get to a node with no children, I check if all the nodes have been visited. If not, I backtrack and explore a different path each time. If I make it back it back to the original node or if I hit a node with no children, I can check if I have seen all the nodes. If not, I return that there is no such path, else I have found a path.

Would this work?

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Feb 21 '18 at 1:46
  • $\begingroup$ The way to tell whether your algorithm works is to prove it correct, or find a counterexample. A good place to start would be to try running your algorithm by hand on a bunch of some example graphs, then see if you spot any patterns that lets you prove it correct or construct a counterexample. If you're still stuck, you could try testing it on a million randomly generated graphs to see if it always gives the correct answer, to help you formulate a reasonable conjecture about whether you think it always works or doesn't. $\endgroup$ – D.W. Feb 21 '18 at 1:47
4
$\begingroup$

The problem is how to deal with visited vertex.

If you keep following, the time complexity is not linear because of repeated visiting. Otherwise, your algorithm will fail in the following simple example:

1 --> 2 -----------> 3 --> 4
        \         /
         --> 5 -->

The first search find 1-2-3-4, then it goes back to 2 and find 1-2-5-3. Now because 3 is visited, the search stops, and thus finally fails.

A hint (or answer) to solve the problem: performing a topological ordering firstly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.