DFS算法遍历

Question

鉴于上图,带有堆栈的DFS遍历为我提供了以下路径......

1-2-3-4-5-6

以上路径是否有效？还有另一条路吗？(我的教科书给了我1-2-3-6-4-5)

我没有足够的代表在计算机科学堆栈上发布图像所以我不得不求助于此,不确定它是否合适; 如果不是,我很乐意随后将其删除.

谢谢,

Answer 1

您已经列出了图表的完全有效的DFS遍历,并且教科书为您提供了另一个完全合法的图表DFS遍历.同一个图表中可能存在许多深度优先遍历(实际上,它们通常指数级很多),所以如果你没有得到与教科书相同的那个并不是直接引起警报的原因.

以下是其他一些排序:

1 2 5 4 3 6
3 1 6 2 5 4
5 4 2 3 1 6
...

但是,如果有关于如何访问节点的其他规则(例如,始终按升序或降序访问连接的节点),则DFS搜索将始终生成相同的输出.

希望这可以帮助!