深入理解与实现：Java中BFS算法计算最短路径的正确姿势

// ...
nextNodeMap.put(currentNode, nextNode); // 问题所在：可能覆盖
// ...
for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
    directions.add(node);
}

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Node {
    private final int value;
    private final Set<Node> siblingNodes = new HashSet<>();

    public Node(int value) {
        this.value = value;
    }

    public Set<Node> getSiblingNodes() {
        return siblingNodes;
    }

    public int getValue() {
        return value;
    }

    public void addSiblingNode(Node node) {
        siblingNodes.add(node);
    }

    @Override
    public boolean equals(Object o) {
        // 检查对象是否为自身
        if (this == o) return true;
        // 检查对象是否为null或类型不匹配
        if (o == null || getClass() != o.getClass()) return false;
        // 类型转换并比较关键字段
        Node other = (Node) o;
        return value == other.value;
    }

    @Override
    public int hashCode() {
        // 使用Objects.hash()生成哈希码，确保与equals方法一致
        return Objects.hash(value);
    }
}

import java.util.*;
import java.util.stream.Collectors;

public class BFSShortestPath {

    /**
     * 使用BFS算法查找从源节点到目标节点的最短路径。
     *
     * @param source      起始节点。
     * @param destination 目标节点。
     * @return 包含最短路径节点的列表，如果不存在路径则返回空列表。
     */
    public static List<Node> getDirections(Node source, Node destination) {
        // paths 映射：键是子节点，值是父节点。它也用于追踪已访问节点。
        Map<Node, Node> paths = new HashMap<>();
        // 使用 ArrayDeque 作为队列，性能优于 LinkedList。
        Queue<Node> queue = new ArrayDeque<>();

        // 初始化：将源节点加入队列，并记录其父节点为null（路径的起点）。
        queue.add(source);
        paths.put(source, null);

        boolean isFound = false; // 标记是否找到目标节点

        // BFS 搜索循环
        while (!isFound && !queue.isEmpty()) {
            Node current = queue.remove(); // 出队当前节点

            // 遍历当前节点的所有邻居
            for (Node sibling : current.getSiblingNodes()) {
                // 如果邻居节点未被访问过（即不在 paths 映射中）
                if (!paths.containsKey(sibling)) {
                    // 记录邻居节点的父节点为当前节点
                    paths.put(sibling, current);
                    // 如果邻居节点就是目标节点，则找到路径
                    if (sibling.equals(destination)) {
                        isFound = true; // 设置标记，终止搜索
                        break;
                    }
                    queue.add(sibling); // 将邻居节点加入队列
                }
            }
        }
        // 调用辅助方法重建路径
        return getPath(source, destination, paths);
    }

    /**
     * 辅助方法：根据父节点映射重建路径。
     *
     * @param start 起始节点。
     * @param end   目标节点。
     * @param paths 父节点映射 (child -> parent)。
     * @return 从起始到目标节点的路径列表，如果不存在路径则返回空列表。
     */
    public static List<Node> getPath(Node start, Node end, Map<Node, Node> paths) {
        List<Node> path = new ArrayList<>();
        Node current = end;

        // 从目标节点开始，通过父节点映射回溯到起始节点
        // 如果 paths 不包含 end 节点，说明 end 不可达
        if (!paths.containsKey(end)) {
            return Collections.emptyList();
        }

        while (current != null) {
            path.add(current);
            // 如果回溯到起始节点，或者路径断裂 (current 无法找到父节点)
            if (current.equals(start)) {
                break;
            }
            current = paths.get(current);
        }

        // 如果回溯未能到达起始节点，说明没有完整路径
        if (current == null || !current.equals(start)) {
            return Collections.emptyList();
        }

        Collections.reverse(path); // 反转列表，使其从起始节点到目标节点
        return path;
    }

    public static void main(String[] args) {
        // 构造示例图
        //        1             -> 5
        // 0 ->           -> 4
        //        2 -> 3        -> 6    -> 7

        Node node0 = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node0.addSiblingNode(node1);
        node0.addSiblingNode(node2);

        Node node3 = new Node(3);
        node2.addSiblingNode(node3);

        Node node4 = new Node(4);
        node3.addSiblingNode(node4);

        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node4.addSiblingNode(node5);
        node4.addSiblingNode(node6);

        Node node7 = new Node(7);
        node6.addSiblingNode(node7);

        // 查找从节点0到节点7的最短路径
        List<Node> shortestPath = getDirections(node0, node7);

        // 打印路径
        if (!shortestPath.isEmpty()) {
            String path = shortestPath.stream()
                .map(Node::getValue)
                .map(String::valueOf)
                .collect(Collectors.joining(" -> "));
            System.out.println("最短路径: " + path);
        } else {
            System.out.println("未找到从节点0到节点7的路径。");
        }

        // 查找从节点0到节点5的路径
        List<Node> pathTo5 = getDirections(node0, node5);
        if (!pathTo5.isEmpty()) {
            String path = pathTo5.stream()
                .map(Node::getValue)
                .map(String::valueOf)
                .collect(Collectors.joining(" -> "));
            System.out.println("最短路径 (0 -> 5): " + path);
        } else {
            System.out.println("未找到从节点0到节点5的路径。");
        }
    }
}

最短路径: 0 -> 2 -> 3 -> 4 -> 6 -> 7
最短路径 (0 -> 5): 0 -> 2 -> 3 -> 4 -> 5