6.2.2 邻接表

邻接表为每个顶点保存出边链表或动态数组，空间 O(V+E)（无向边存两份）。查某条边最坏取决于端点度数，枚举全部邻居总成本与边数成正比，适合稀疏图。

手工状态

有向边 0→1、0→2、2→1：表 0:[1,2]，1:[]，2:[1]。行表长度给出度，却不能直接给入度；需统计所有表或另建逆邻接表。

结构与代码

vector<vector<pair<int,int>>> g(n); g[u].push_back({v,w});

无向边必须同时加入 g[u] 和 g[v]。邻接次序会影响 DFS/BFS 序列，但不影响可达集合。

正确性依据

每条存储弧恰在所属顶点表中出现一次；遍历全部表时，总弧结点数为 E（有向）或2E（无向）。

错解反馈

无向边只加一端；从表长直接求有向入度；把某个固定遍历序列当图的唯一序列。

迁移训练

顶点0邻接表为[3,1,2]，若按存储顺序BFS，第一层访问顺序如何？答案3、1、2；换排序会改变序列。