java迭代DFS以查找从源到目标的路径
如果您能帮助我调试DFS的实现以找到路径,我将不胜感激。我的实现通常运行良好,但在某个边缘情况下,将向算法访问的结果中添加一个额外节点,但不应包含在解决方案中,因为从它到结果列表中下一个节点的路径不存在。问题可能是由where结果引起的。add(nextNode)已定位,但我无法修复此错误
下面是问题的一个示例(任意权重),算法返回[0 2 4 1 3 5]作为结果,即使不存在从4到1的边
有人能建议如何修改我的代码,使像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;
}
# 1 楼答案
每次将节点添加到
result
列表时,将其添加到visited
列表中显然是错误的(访问的节点集不一定只包含路径。它可以有一组其他节点,而不仅仅是一个)要修复它,可以创建一个
parent
列表来存储每个节点的父节点(并在发现新节点时填充它)。这样,您只需要通过父链接从目标节点转到源节点来重建路径