Java入门课：图中两顶点间距离计算代码报错求助

代码中的核心问题 #

• 起始顶点错误：使用了未定义的start变量，应该以输入参数v作为BFS的起点
• 初始化逻辑矛盾：队列添加的是start，但仅标记v为已访问，导致起始点混乱
• 未追踪路径距离：仅记录父节点，没有按BFS的层级计算路径长度，无法得到目标距离
• 未提前终止搜索：找到目标w后未停止遍历，造成不必要的计算
• 语法错误：方法缺少返回语句，无法通过编译
• 边界场景缺失：未处理v与w为同一节点、w不可达的情况

修正后的代码 #

/**
 * Find the distance between two vertices in this graph
 * 
 * The distance between two vertices is the number of edges
 * in a shortest path from one vertex to the other vertex.
 * 
 * @param v The first vertex
 * @param w The second vertex
 * @return the distance between v and w, returns -1 if w is unreachable from v
 */
public int distance(String v, String w) {
    // 处理同一节点的边界情况
    if (v.equals(w)) {
        return 0;
    }

    DSHashMap<String> visited = new DSHashMap<>();
    LinkedList<String> queue = new LinkedList<>();
    // 用哈希表记录每个节点到起点的距离
    DSHashMap<Integer> distanceMap = new DSHashMap<>();

    // 初始化起点
    queue.add(v);
    visited.put(v, "");
    distanceMap.put(v, 0);

    while (!queue.isEmpty()) {
        String current = queue.removeFirst();
        // 防止graph.get返回null导致空指针
        if (graph.get(current) == null) {
            continue;
        }
        for (String neighbor : graph.get(current)) {
            if (visited.containsKey(neighbor)) {
                continue;
            }
            // 计算邻居节点的距离：当前节点距离+1
            int neighborDistance = distanceMap.get(current) + 1;
            // 找到目标节点，直接返回距离
            if (neighbor.equals(w)) {
                return neighborDistance;
            }
            visited.put(neighbor, "");
            distanceMap.put(neighbor, neighborDistance);
            queue.add(neighbor);
        }
    }

    // 如果遍历完都没找到w，说明不可达，返回-1（或根据课程要求调整）
    return -1;
}

关键修改说明 #

1. 边界处理：先判断v和w是否为同一节点，直接返回0
2. 距离追踪：新增distanceMap记录每个节点到起点的距离，避免通过父节点回溯计算
3. 提前终止：遍历到目标节点w时立即返回距离，提升效率
4. 空指针防护：判断graph.get(current)是否为null，避免遍历空集合
5. 逻辑统一：队列和访问标记都以v作为起点，修正初始化矛盾
6. 完善返回逻辑：处理不可达场景，返回-1（可根据课程要求调整为0或其他值）

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