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

Question

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

问题的示例附在下面（权重任意），即使不存在从 4 到 1 的边，结果算法 returns [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;
        }

Answer 1

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

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

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

Iterative DFS to find path from source to destination

java

algorithm

graph-theory