gpt4 book ai didi

java - 迭代 DFS 以查找从源到目标的路径

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:57:37 35 4
gpt4 key购买 nike

我将不胜感激帮助调试我的 DFS 实现以找到路径。我的实现通常运行良好,但在某些边缘情况下会向算法访问的结果添加一个额外的节点,但不应包含在解决方案中,因为从它到结果列表中下一个节点的路径不存在。这个问题很可能是由 Result.add(nextNode) 的位置引起的,但我一直无法修复这个错误。

问题的示例附在下面(权重任意),即使不存在从 4 到 1 的边,算法也会返回 [0 2 4 1 3 5] 作为结果。

Example

有人可以建议如何修改我的代码,以便不将像 4 这样的节点添加到结果中吗?

 public static ArrayList<Integer> pathDFS(Integer source, Integer destination, WeightedGraph graph) {
ArrayList<Integer> Result = new ArrayList<Integer>();
ArrayList<Integer> Visited = new ArrayList<Integer>();
Stack<Integer> s = new Stack<>();
s.push(source);
Visited.add(source);
while (!s.isEmpty()) {
Integer v = s.pop();
for (int nextNode : getAdjacentNodes(v, graph)) {
if (!Visited.contains(nextNode)) {
s.push(nextNode);
Visited.add(nextNode);
**Result.add(nextNode);**
if (nextNode == destination)
return Result;
}
}
}
return Result;
}

最佳答案

每次将节点添加到visited列表时都将节点添加到result列表显然是错误的(访问节点的集合不一定只包含路径。它可以有一堆其他节点,而不仅仅是一个)。

要修复它,您可以创建一个parent 列表来存储每个节点的父节点(并在发现新节点时填充它)。这样,您只需要从目标节点通过父链接到源节点即可重构路径。

关于java - 迭代 DFS 以查找从源到目标的路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43021579/

35 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com