java - 有向图的深度优先遍历

Question

我有一个作业，我必须编写一个方法来执行有向图的 DFT。以下是有向边:

• 节点1-->节点2、节点3

• 节点 2 -->节点 4

• 节点 3 -->节点 5

• 节点4-->节点5

据我了解，看完this video ，从节点 1 开始对上图进行 DFT 将输出 1、2、4、5、3。我对此的推理是，当查看 1 的边缘时，2 自然会先于 3，然后线性前进直到到达在 5。由于 5 除了连接到 4 之外没有任何其他边缘，因此遍历将“展开”回到节点 1，之后它将输出节点 3。

但是，作业期望输出 1、3、5、4、2。我的逻辑中的问题在哪里？

编辑:我不确定我误解了赋值的哪一部分，但解决方案是在打印第一个元素后，遍历一个节点将其添加到堆栈中，但预期的输出是元素离开堆栈的顺序.在图形中导航，您从节点 1 开始，首先移动到节点 2(因为分配要求您按自然顺序在节点之间进行选择)，然后将节点 2 添加到堆栈中。然后继续遍历节点 2 指向的节点，导致你的堆栈为 2、4、5。然后，返回 2 和 3 之间的选择，将 3 添加到堆栈，弹出堆栈的每个元素，输出他们随你去。因此，首先打印 1，然后弹出堆栈的元素，得到 3、5、4、2。

Answer 1

我相信你的逻辑是正确的，正确答案是1,2,4,5,3。作业一定有错误。

请记住，如果节点 3 在节点 2 之前被访问过，那么 {1,3,5,2,4} 也是一个可接受的答案。