Depth-first traversal of a directed graph

1
votes

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.

2
javagraphdepth-first-searchdirected-graph

2 Answers

3
votes

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.

3
votes

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