用广度优先搜索法寻找最短路径节点

Question

我正在上面的图上运行广度优先搜索，查找从节点0到节点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 ALGO通过的节点。遍历以到达节点6，如[0,3,2,5,6]。为此，我创建了一个名为ShortestPath的列表&试图存储访问节点的前一个节点，以获得节点列表。转介

Answer 1

将所有访问的节点存储在一个列表中无助于找到最短路径，因为最终您无法知道哪些节点是通向目标节点的节点，哪些节点是死胡同。

您需要做的是每个节点将前一个节点存储在起始节点的路径中。

因此，创建一个映射map parentnodes ，而不是这样：

shortestPath.add(nextNode);

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);
}