我有一个作业,必须编写一个执行有向图的 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
,(2)比(1)更有效。