Java中如何修改Map列表内节点的邻接列表

问题分析 #

你的代码存在两个核心问题：

• addNode方法逻辑错误：node.put(id, new ArrayList<>())返回的是该ID之前关联的旧值，第一次添加节点时这个值是null，导致graph列表里存的全是无效的null。
• 冗余的graph列表：node这个Map本身就可以通过节点ID直接定位到对应的邻接列表，额外维护graph完全没必要，反而增加了操作复杂度。

修正方案 #

直接基于node Map实现图结构，删掉无用的graph列表：

1. 修正数据结构定义

public static Map<Integer, List<Integer>> node = new HashMap<>();
// 移除graph列表，不需要额外维护

2. 正确实现节点创建方法

先判断节点ID是否已存在，不存在则创建新的邻接列表：

public static void addNode(int id) {
    // 仅当节点不存在时，创建新的空邻接列表
    node.putIfAbsent(id, new ArrayList<>());
}

3. 实现边添加方法

通过节点ID从Map中取出邻接列表，直接添加目标节点ID即可，同时确保源节点已存在：

public static void addVertice(int k, int v) {
    // 先保证源节点k存在，不存在则自动创建
    addNode(k);
    // 取出k对应的邻接列表，添加目标节点v
    node.get(k).add(v);
    
    // 如果是无向图，需要给v的邻接列表也添加k，可选：
    // addNode(v);
    // node.get(v).add(k);
}

原代码失效原因 #

你之前的addVertice方法逻辑完全混乱：

• graph.get(k)取到的是null（因为addNode存的是null），调用put会直接触发空指针异常。
• add(v)不是合法的Java方法，你想调用列表的add，但根本没拿到对应的列表对象。

测试示例 #

public static void main(String[] args) {
    addNode(1);
    addNode(2);
    addVertice(1, 2);
    addVertice(1, 3); // 自动创建节点3的邻接列表
    
    System.out.println(node.get(1)); // 输出 [2, 3]
    System.out.println(node.get(2)); // 输出 []
    System.out.println(node.get(3)); // 输出 []
}

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