Java中BFS最短路径算法的正确实现与常见陷阱

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 int getValue() {
        return value;
    }

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

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

    /**
     * 正确覆盖 Object.equals(Object o) 方法。
     * 用于比较两个 Node 对象是否逻辑相等，基于它们的 value 属性。
     *
     * @param o 待比较的对象
     * @return 如果对象相等则返回 true，否则返回 false
     */
    @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;
    }

    /**
     * 覆盖 equals 方法时，必须同时覆盖 hashCode 方法。
     * 返回基于 Node 对象的 value 属性计算的哈希码。
     *
     * @return 对象的哈希码
     */
    @Override
    public int hashCode() {
        return Objects.hash(value);
    }
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
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; // 标记是否找到目标节点

        while (!isFound && !queue.isEmpty()) {
            Node current = queue.remove(); // 从队列中取出当前节点

            // 遍历当前节点的所有邻居节点
            for (Node sibling : current.getSiblingNodes()) {
                // 如果邻居节点已经存在于 paths 映射中，说明它已被访问，跳过。
                if (paths.containsKey(sibling)) {
                    continue;
                }

                // 记录邻居节点的父节点为当前节点。
                paths.put(sibling, current);

                // 如果找到目标节点，设置标记并终止当前节点的邻居遍历。
                if (sibling.equals(destination)) {
                    isFound = true;
                    break;
                }

                // 将邻居节点加入队列，以便后续探索。
                queue.add(sibling);
            }
        }

        // 调用辅助方法重建路径
        return getPath(source, destination, paths);
    }

    // ... (getPath 方法将在下一节介绍)
    // ... (main 方法将在后续示例中展示)
}

// ... (接 BFSShortestPath 类)

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

        // 从目标节点开始回溯，直到到达源节点或路径中断
        // current != null 检查处理了目标节点无法从源节点到达的情况
        // !current.equals(start) 确保循环在到达源节点前停止，避免重复添加源节点
        while (current != null && !current.equals(start)) {
            path.add(current); // 将当前节点添加到路径中
            current = paths.get(current); // 获取当前节点的父节点
        }

        // 如果 current 最终是源节点，说明路径存在，将源节点加入路径
        if (current != null && current.equals(start)) {
            path.add(start);
        } else {
            // 如果 current 变为 null，表示从 end 无法到达 start
            return Collections.emptyList(); // 返回空列表
        }

        // 由于是反向构建的路径（从目标到源），需要反转列表以得到正确的顺序
        Collections.reverse(path);
        return path;
    }

// ... (BFSShortestPath 类结束)