algorithm - 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 搜索将始终产生相同的输出。

希望这可以帮助！

Answer 2

您描述的输出不是路径，而是 DFS 访问节点的顺序。路径是节点列表，其中每个节点都连接到前一个节点和下一个节点。

DFS 遍历的输出也可以看作是 DFS 遍历树，在您的情况下对应于：

1 - 2 - 3 - 4 - 5
        |
        6

教科书树是

1 - 2 - 3 - 6 
        |
        4 - 5

您可以获得许多不同的 DFS 树，因为在您可以选择的每个点上，您都可以决定先去哪里。在您的示例中，您可以从节点 3 转到节点 4 或节点 6，不同的输出是由于不同的选择。