给定上述图形，使用堆栈的DFS遍历给出以下路径...
1-2-3-4-5-6
上述路径是否有效？是否存在另一条路径？（我的教科书给出了1-2-3-6-4-5）
我没有足够的声望在计算机科学堆栈上发布图片，所以不得不求助于这里，请问这个问题是否适合在这里提问？如果不合适，我很乐意之后将其删除。
谢谢！
2个回答
6
你列出的图的DFS遍历方式是完全有效的，而教科书中给你的另一种DFS遍历方式也是合法的。同一个图可以有许多深度优先遍历方式（实际上，通常会有指数级别的遍历方式），所以如果你得到的不是和教科书相同的遍历方式，并不是立即引起警报的原因。
以下是其他的排序方式：
以下是其他的排序方式：
1 2 5 4 3 6
3 1 6 2 5 4
5 4 2 3 1 6
...
然而，如果有其他规则指定节点访问顺序（例如总是按升序或降序访问连接的节点），那么深度优先搜索将始终产生相同的输出。
希望这可以帮到您！
- templatetypedef
1
太棒了，谢谢！我学习时发现访问节点的顺序很重要，我猜教科书上的假设可能不同。 - user1234440
1
您所描述的输出不是路径，而是DFS遍历节点的顺序。路径是一个节点列表，其中每个节点都与前一个和后一个节点相连。
DFS遍历的输出也可以看作是DFS遍历树，这在您的情况下对应于：
1 - 2 - 3 - 4 - 5
|
6
教科书树是
1 - 2 - 3 - 6
|
4 - 5
你可以得到许多不同的DFS树，因为在每个决策点上，你都可以决定先走哪条路。在你的例子中，从节点3可以走向节点4或节点6，而不同的输出结果是由于不同的选择所导致的。
- Dejan Jovanović
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接