这个图上的 DFS 产生的解决方案路径是什么
比格兹
在该图上使用 DFS，按以下顺序访问节点（对于多个后继节点，节点按字母顺序推送到“边界”）：
S->A->E->D->F->G
该访问顺序也是解决方案路径吗？如果是，为什么不是 S->A->E->G，因为 G 也是 E 的后继节点？
PS：我是算法新手，所以如果我显然不理解这个概念，请告诉我。
凯里
如果您正在访问节点，则 DFS 方法将根据邻接表的创建顺序遍历图。
例如，插入 nodeE的后继者的顺序可能是以下几种方式：
1- E-> D, G
2- E-> G, D
在第一种方式中，您将遍历D->F->G或D->G直接，在这两种情况下，您都将G在遍历任何节点E其他后继节点之前访问节点，因此您将无法遍历路径，S->A->E->G因为节点G之前已经从节点D或访问过F。
在第二种方式中，您将E->G直接遍历，因此这将导致遍历 path S->A->E->G，但您将无法G从 node访问nodeD或者F因为它已经从 node 访问E。
如果您使用 true 或 false 访问，则会发生前面的情况，但是如果您尝试使用边上的成本找到最短路径，那么您将需要使用Dijkstra的算法来查找图形上的最短路径，并且您可以如果您不熟悉它，请在此处阅读更多相关信息。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
在大图上运行DFS
- 2
完成图上的 DFS 扫描
- 3
这个幼稚的解决方案的最大功能是什么？
- 4
为什么这个 Python 解决方案不是就地解决方案？
- 5
这个FizzBuzz解决方案中的明星（*）在做什么？
- 6
DFS + Memoized 解决方案在 LeetCode 上获取 TLE
- 7
这个红色正方形图标在Visual Studio 2013解决方案资源管理器中是什么意思？
- 8
这个红色正方形图标在Visual Studio 2013解决方案资源管理器中是什么意思？
- 9
如何纠正这个python dfs搜索？
- 10
为什么这个通用祖先解决方案具有更好的最坏情况性能？
- 11
为什么这个共同的祖先解决方案具有更好的最坏情况下的性能？
- 12
为什么这个背包问题的解决方案不起作用？
- 13
LeetCode的“迷宫II”问题：为什么这个解决方案会超过时间限制？
- 14
更好的将数据加载到地图上的解决方案
- 15
这个解决方案是否足以阻止 SQL 注入
- 16
这个问题有更优雅的解决方案吗？
- 17
我可以简化这个解决方案吗？
- 18
我不明白这个练习的解决方案
- 19
使用DFS解决8难题
- 20
迷宫路径搜索DFS Java
- 21
该查询的解决方案是什么？
- 22
我不知道为什么这个for循环程序不起作用（python）。解决方案？
- 23
什么是针对该算法的更优化的解决方案？我觉得我可以从这个问题中学到更多
- 24
使用迭代DFS而不是递归DFS的第一个DFS路径
- 25
我不理解这个 dfs 实现的语法
- 26
解决这个矩阵的正确方法是什么
- 27
为什么 fmincon 产生不同的解决方案
- 28
有人可以提出动态编程解决方案来解决这个问题吗？
- 29
请找到此查询的解决方案我该如何解决这个问题
我来说两句