最轻量图建模用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()) ——这步很多人忘了。
