Java课程作业SocialGraph类knowsWithDegree方法异常排查求助

需求背景 #

课程作业要求实现两个Java类：

• SocialGraph类：定义人与人之间的有向社交关系（即A认识B是单向关系），提供关系的增删查操作
• SocialGraphTest类：验证关系查询逻辑，尤其是指定度数的关系查询功能

问题定位 #

经排查，故障出在knowsWithDegree方法，原方法存在以下核心问题：

1. 硬编码仅适配4个节点的场景，节点数量超过4会触发数组越界异常，无通用性
2. 类型逻辑错误：map.get(a).contains(map.get(keys[0]).contains(b))中，内层contains返回的是布尔值，用存储字符串的List去判断是否包含布尔值，逻辑完全不成立
3. 仅支持1度、2度关系判断，度数参数大于2时永远返回错误结果

修复思路 #

采用**广度优先搜索（BFS）**遍历有向图，计算起点a到终点b的最短路径长度，判断是否等于指定度数x即可，同时兼容任意节点数量、任意度数的查询需求。

修复后完整代码 #

import java.util.*;

public class SocialGraph {

    private HashMap<String, List<String>> map = new HashMap<>();
    
    public SocialGraph() {
        map = new HashMap<>();
    }
    
    public void addIndividual(String a) {
        if (!map.containsKey(a)) {
            map.put(a, new ArrayList<>());
        }
    }
    
    public boolean hasKnowsArrow(String a, String b) {
        return map.containsKey(a) && map.get(a).contains(b);
    }
    
    public void addKnowsArrow(String a, String b) {
        if (map.containsKey(a) && map.containsKey(b) && !hasKnowsArrow(a, b)) {
            map.get(a).add(b);
        }
    }
    
    public void removeKnowsArrow(String a, String b) {
        if (map.containsKey(a) && map.containsKey(b) && hasKnowsArrow(a, b)) {
            map.get(a).remove(b);
        }
    }
    
    // 修复后的knowsWithDegree方法
    public boolean knowsWithDegree(String a, String b, int x) {
        // 边界校验
        if (x < 1 || !map.containsKey(a) || !map.containsKey(b)) {
            return false;
        }
        // 1度关系直接判断
        if (x == 1) {
            return hasKnowsArrow(a, b);
        }
        // BFS遍历记录访问过的节点和当前度数
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.addAll(map.get(a));
        visited.add(a);
        int currentDegree = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            currentDegree++;
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                if (current.equals(b)) {
                    return currentDegree == x;
                }
                if (!visited.contains(current)) {
                    visited.add(current);
                    for (String neighbor : map.get(current)) {
                        if (!visited.contains(neighbor)) {
                            queue.add(neighbor);
                        }
                    }
                }
            }
            // 超过指定度数直接返回
            if (currentDegree > x) {
                return false;
            }
        }
        // 无可达路径
        return false;
    }
}

class SocialGraphTest {
    public static void main(String[] args) {
        SocialGraph socialGraph = new SocialGraph();
        socialGraph.addIndividual("Anne");
        socialGraph.addIndividual("Daisy");
        socialGraph.addIndividual("Bob");
        socialGraph.addIndividual("Charlie");

        socialGraph.addKnowsArrow("Anne", "Bob");
        socialGraph.addKnowsArrow("Anne", "Daisy");
        socialGraph.addKnowsArrow("Bob", "Daisy");
        socialGraph.addKnowsArrow("Bob", "Charlie");

        System.out.println(socialGraph.hasKnowsArrow("Anne", "Bob")); // true
        System.out.println(socialGraph.hasKnowsArrow("Anne", "Daisy"));// true
        System.out.println(socialGraph.hasKnowsArrow("Bob", "Daisy"));// true
        System.out.println(socialGraph.hasKnowsArrow("Bob", "Charlie"));// true
        System.out.println(socialGraph.hasKnowsArrow("Anne", "Charlie")); // false

        System.out.println();

        System.out.println(socialGraph.knowsWithDegree("Anne", "Daisy", 1)); // true
        System.out.println(socialGraph.knowsWithDegree("Anne", "Charlie", 2)); // true（Anne->Bob->Charlie）
        System.out.println(socialGraph.knowsWithDegree("Anne", "Daisy", 3)); // false
    }
}

测试结果说明 #

运行测试类后输出完全符合预期：

• 1度关系查询Anne认识Daisy返回true
• 2度关系查询Anne认识Charlie返回true（路径为Anne->Bob->Charlie）
• 3度关系查询Anne认识Daisy返回false，无对应长度的可达路径

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