我有一个作业，必须编写一个执行有向图的 DFT 的方法。这是有向边：
节点1-->节点2、节点3
节点 2 --> 节点 4
节点 3 --> 节点 5
节点4-->节点5
根据我的理解，观看这个视频后，从节点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。
我相信你的逻辑是正确的，正确答案是1,2,4,5,3。作业肯定有错误。
请记住，如果节点 3 在节点 2 之前被访问，那么 {1,3,5,2,4} 也将是一个可接受的答案。
你的逻辑没有任何问题。您的结果与预期输出 (1) 一样有效。
我对此的推理是，当查看 1 的边缘时，2 会 自然先于3
图中没有任何内容支持这种排序或另一种排序。所以这取决于你想先遵循两条边中的哪一条。
（1）读完Gabriel的回答后，我不得不承认我没有看到“预期输出”中明显的错误：
如果从节点 1 开始，我们先访问 3，再访问 2，然后再访问 5，则回溯将带我们回到节点 1，并且从那里开始必须先是 2，然后是 4：{1, 3, 5, 2, 4} 而不是 {1, 3, 5, 4, 2}。
所以，你作业中的答案（正如其他人指出的）是错误的。应该是 {1,3,5,2,4}。
现在，这个答案可能是首选的原因是因为它使用了
stack-space如果您绘制两个答案的 DFT，即 (1) - {1, 2, 4, 5, 3} 和 (2) - {1,3,5,2,4}。 (1) 中的级别数为 4，(2) 中的级别数为 3。
我们知道，与另一层相比，层数较少的层将具有更少的堆栈空间。
因此，如果我们牢记
stack-space