有向图的深度优先遍历

问题描述 投票:0回答:3

我有一个作业,必须编写一个执行有向图的 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。

java graph depth-first-search directed-graph
3个回答
3
投票

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

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


3
投票

你的逻辑没有任何问题。您的结果与预期输出 (1) 一样有效。

我对此的推理是,当查看 1 的边缘时,2 会 自然先于3

图中没有任何内容支持这种排序或另一种排序。所以这取决于你想先遵循两条边中的哪一条。


(1)读完Gabriel的回答后,我不得不承认我没有看到“预期输出”中明显的错误:

如果从节点 1 开始,我们先访问 3,再访问 2,然后再访问 5,则回溯将带我们回到节点 1,并且从那里开始必须先是 2,然后是 4:{1, 3, 5, 2, 4} 而不是 {1, 3, 5, 4, 2}。


0
投票

所以,你作业中的答案(正如其他人指出的)是错误的。应该是 {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)更有效。

© www.soinside.com 2019 - 2024. All rights reserved.