通过广度优先搜索找到最短路径节点

Question

我正在上图上进行广度优先搜索，以找到从Node 0到的最短路径Node 6。

我的密码

public List<Integer> shortestPathBFS(int startNode, int nodeToBeFound){
        boolean shortestPathFound = false;
        Queue<Integer> queue = new LinkedList<Integer>();
        Set<Integer> visitedNodes = new HashSet<Integer>();
        List<Integer> shortestPath = new ArrayList<Integer>();
        queue.add(startNode);
        shortestPath.add(startNode);

        while (!queue.isEmpty()) {
            int nextNode = queue.peek();
            shortestPathFound = (nextNode == nodeToBeFound) ? true : false;
            if(shortestPathFound)break;
            visitedNodes.add(nextNode);
            System.out.println(queue);
            Integer unvisitedNode = this.getUnvisitedNode(nextNode, visitedNodes);

            if (unvisitedNode != null) {
                    queue.add(unvisitedNode);
                    visitedNodes.add(unvisitedNode);
                    shortestPath.add(nextNode); //Adding the previous node of the visited node 
                    shortestPathFound = (unvisitedNode == nodeToBeFound) ? true : false;
                    if(shortestPathFound)break;
                } else {
                    queue.poll();
                }
        }
        return shortestPath;
    }

我需要跟踪BFS算法所经过的节点。遍历以到达节点6，例如[0,3,2,5,6]。为此，我创建了一个名为shortestPath＆的列表，并尝试存储所访问节点的先前节点，以获取节点列表。被推荐

但这似乎不起作用。最短的路径是[0,3,2,5,6]

在列表中我得到的是 Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]

这是部分正确的，但可以提供额外的收益1。

If I again start from the first element 0 of the shortestPath list & start
traversing & backtracking. Like 1 doesn’t has an edge to 3, so I backtrack
& move from 0 to 3 to 5, I will get the answer but not sure if that’s
the correct way.

What is the ideal way to getting the nodes for the shortest path?

Answer 1

将所有访问的节点存储在单个列表中对于查找

最短路径，因为最终你无法知道哪些节点是

哪些是指向目标节点的，哪些是死胡同。

您需要做的是让每个节点在路径中存储上一个节点

从起始节点开始。

因此，创建一个map map<Integer，Integer>parentNodes，而不是这样：

shortestPath.add(nextNode);

do this:

parentNodes.put(unvisitedNode, nextNode);

到达目标节点后，可以遍历该映射以找到返回起始节点的路径：

if(shortestPathFound) {
    List<Integer> shortestPath = new ArrayList<>();
    Integer node = nodeToBeFound;
    while(node != null) {
        shortestPath.add(node)
        node = parentNodes.get(node);
    }
    Collections.reverse(shortestPath);
}