Java集合实现图结构：邻接表与Map+List建模教程

最轻量图建模用Map<Integer, List<Integer>>，须用computeIfAbsent初始化List防NPE；带权则用Map<Integer, List<int[]>>；遍历时删边需Iterator或批量remove；小范围连续编号优先用int[][]数组；并发写需节点级锁或CopyOnWriteArrayList。

用 Map<Integer, List<Integer>> 建邻接表，别直接套 HashMap 就完事

Java 里最轻量的图建模方式就是 Map 套 List，但直接写 new HashMap<>() 容易在增删边时触发 NullPointerException——因为没初始化对应节点的 List。

正确做法是每次访问前确保 List 存在：

• 插入边 u → v 时，先检查 graph.get(u) 是否为 null，是则 put(u, new ArrayList<>())
• 更稳妥的是用 computeIfAbsent： graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v)
• 如果图带权，就换成 Map<Integer, List<int[]>>，其中 int[2] 存 {v, weight}，避免封装类开销

遍历时别在 for-each 里改 List，否则 ConcurrentModificationException

DFS/BFS 过程中常要动态删边（比如拓扑排序删入度为 0 的节点所连出的边），但直接在 for (int v : graph.get(u)) 里调 remove() 会炸。

根本原因是 ArrayList 的迭代器是 fail-fast 的，而 computeIfAbsent 返回的也是普通 ArrayList。

• 安全删法：用 Iterator 遍历并调 it.remove()
• 或者先收集待删节点，循环结束后批量 removeAll()
• 如果频繁删边，考虑换 LinkedHashSet 代替 List，remove() 是 O(1)，但内存略高

Integer 作键有装箱开销，小范围图优先用 int[] 数组模拟

节点编号若连续且已知上限（比如 1~10000），用 List<Integer>[] graph = new ArrayList[n+1] 比 Map 快不少；但注意 Java 不允许泛型数组，得加 @SuppressWarnings("unchecked")。

更干净的做法是用原始类型数组：List<Integer>[] graph → 改成 int[][] graph，每个 graph[u] 是一维数组存邻居，长度固定或用额外 int[] size 记录实际边数。

• 优势：无装箱、GC 压力小、缓存局部性好
• 代价：不支持动态加点，扩容麻烦（得手动 Arrays.copyOf）
• 适用场景：竞赛题、离线图、顶点数确定的图算法（如 Dijkstra、Floyd）

多线程读写必须加同步，但别锁整个 Map

并发环境下，多个线程同时往不同节点加边，如果只用 ConcurrentHashMap，仍可能因 computeIfAbsent + add 非原子而出错。

例如两个线程同时对节点 u 调 computeIfAbsent，可能都创建新 ArrayList，后者覆盖前者，导致丢边。

• 简单方案：对每个节点的 List 单独加锁，比如用 ConcurrentHashMap<Integer, Object> locks 管理每节点的锁对象
• 更高效：用 ConcurrentHashMap<Integer, CopyOnWriteArrayList<Integer>>，读多写少时合适，但写操作复制整个数组，边多时不划算
• 真要高性能并发图结构，建议直接上 GraphJin 或 JGraphT，自己手撸容易漏边界

图建模最麻烦的从来不是怎么存，而是“什么时候该初始化”和“谁负责清理”。尤其是稀疏图里大量节点只出不进，Map 键集会悄悄膨胀，得定期 keySet().removeIf(k -> graph.get(k).isEmpty()) ——这步很多人忘了。