请帮忙排查字符串节点图两点间BFS最短路径算法的问题

现存核心问题 #

• 路径记录逻辑错误：你当前用network列表存储的是BFS的遍历顺序，而非两点之间的最短路径。比如A连接B、C，B连接D的场景下，A到D的最短路径是A→B→D，但按你的代码会输出A→B→C→D，完全不符合路径要求。
• 缺少入参合法性校验：没有提前判断start、stop节点是否存在于图的顶点集合中，如果传入不存在的节点，执行map.get(vertex)时会直接抛出空指针异常，代码中断运行，自然不会走到Not found的输出分支，这就是你说无路径时不进入对应分支的核心原因。
• 无提前终止逻辑：哪怕已经找到目标节点，代码还是会遍历完所有从start可达的节点，存在不必要的性能损耗。

修复后的BFS代码 #

public void BFS(String start, String stop) {
    // 先校验节点是否存在
    if (!map.containsKey(start) || !map.containsKey(stop)) {
        System.out.println("Not found.");
        return;
    }
    // 起止点相同直接返回
    if (start.equals(stop)) {
        System.out.println("Route Path: ");
        System.out.println(start);
        return;
    }

    Queue<String> queue = new ArrayDeque<>();
    HashSet<String> seen = new HashSet<>();
    // 新增前驱映射，记录每个节点的前一个节点，用于回溯路径
    Map<String, String> prev = new HashMap<>();
    queue.add(start);
    seen.add(start);
    boolean found = false;

    while (!queue.isEmpty()) {
        String vertex = queue.poll();
        // 遍历当前节点的所有邻居
        for (String neighbor : map.get(vertex)) {
            if (!seen.contains(neighbor)) {
                prev.put(neighbor, vertex);
                // 找到目标节点直接终止遍历
                if (neighbor.equals(stop)) {
                    found = true;
                    break;
                }
                seen.add(neighbor);
                queue.add(neighbor);
            }
        }
        if (found) break;
    }

    if (found) {
        // 回溯构建路径
        List<String> path = new ArrayList<>();
        String curr = stop;
        while (curr != null) {
            path.add(curr);
            curr = prev.get(curr);
        }
        // 反转得到从start到stop的顺序
        Collections.reverse(path);
        // 输出路径
        System.out.println("Route Path: ");
        for (int i = 0; i < path.size(); i++) {
            if (i == path.size() - 1) {
                System.out.println(path.get(i));
            } else {
                System.out.print(path.get(i) + " -> ");
            }
        }
    } else {
        System.out.println("Not found.");
    }
}

修复效果说明 #

• 新增的入参校验避免了空指针异常，不存在的节点会直接返回Not found
• 前驱映射+回溯逻辑可以输出正确的最短路径，而非遍历顺序
• 提前终止逻辑减少了不必要的节点遍历
• 无可达路径时found变量为false，会正常进入Not found输出分支

内容的提问来源于stack exchange，提问作者M.M.