Depth-first traversal of a directed graph

Question

I have an assignment where I have to write a method that performs a DFT of a directed graph. Here are the directed edges:

• Node 1-->Node 2, Node 3

• Node 2 -->Node 4

• Node 3 -->Node 5

• Node 4-->Node 5

From my understanding, after watching this video, doing a DFT of the above graph starting from Node 1 would output 1, 2, 4, 5, 3. My reasoning for this is that when looking at 1's edges, 2 would naturally come before 3, and then progresses linearly until it arrives at 5. Since 5 doesn't have any other edges besides it's connection to 4, the traversal would "unwind" back to Node 1, after which it would output Node 3.

However, the assignment is expecting the output 1, 3, 5, 4, 2. Where is the problem in my logic?

EDIT: I'm not sure what part of the assignment I misunderstood but the solution was that after printing the first element, traversing a node adds it to a stack, but the expected output is the order in which elements leave the stack. Navigating the graph, you start with Node 1 and travel to Node 2 first (because the assignment demands that you choose between nodes in their natural order), adding Node 2 to the stack. You then continue traversing the Nodes that Node 2 leads to, leading your stack to be 2, 4, 5. Then, returning to the choice between 2 and 3, you add 3 to the stack, pop off each element of the stack, outputting them as you go. Thus, 1 is printed first, then popping off the elements of the stack, you get 3, 5, 4, 2.

Answer 1

So, the answer in your assignment (as pointed out by others) is wrong. It should have been {1,3,5,2,4}.

Now, the reason why THIS answer might be preferred is because of the stack-space it uses.

If you draw the DFT for both the answers, i.e., (1) - {1, 2, 4, 5, 3} and (2) - {1,3,5,2,4}. The number of levels in (1) is 4 and (2) is 3.

We know the one with less number of levels will have less stack-space compared to the other one.

Hence, if we keep stack-space in mind (2) is little-bit more efficient then (1).

Answer 2

There's nothing wrong with your logic. Your result is just as valid as the expected output (1).

My reasoning for this is that when looking at 1's edges, 2 would naturally come before 3

There's nothing in the graph to support either this or another ordering. So it's up to you which of the two edges you want to follow first.

---

(1) After reading Gabriel's answer, I have to admit that I didn't see the apparent mistake in the "expected output":

If, starting from node 1, we visit 3 before 2 and then follow to the 5, backtracking will lead us back to node 1, and from there it must first be 2 and then 4: {1, 3, 5, 2, 4} and not {1, 3, 5, 4, 2}.

Answer 3

I believe your logic is correct, and the correct answer is 1,2,4,5,3. The assignment must have a mistake.

Keep in mind that if node 3 was visited before node 2, then {1,3,5,2,4} would also be an acceptable answer.