01先读懂这个概念
先约定图描述什么
有四个房间 0、1、2、3，走廊连接 0–1 和 0–2，房间 3 没有走廊。每个房间是节点（vertex），每条走廊是边（edge）。记节点数为 V=4，边数为 E=2。没有边的房间仍然存在，不能只从边列表猜测节点集合。
双向走廊用无向边，单行路用有向边，行驶时间是边权。问『能不能到』只关心连通；问『最少经过几条路』关心边数；问『总耗时最少』关心权重。它们需要的算法可能不同。
邻接表保存每个节点的直接邻居
建一个长度为 V 的列表，每一项也是列表。无向边 0–1 要同时写入 graph[0].append(1) 与 graph[1].append(0)，因为两个方向都能走。房间 3 对应空列表，而不是从结构里消失。
邻接矩阵则为每对节点保存是否相邻，常用 V×V 的表。邻接表适合边较少的图，枚举一个节点的邻居只需遍历它的列表；矩阵查询某一条边很直接，但枚举邻居一般要检查整行 V 项。不存在对所有问题都最好的存法。
02从具体数据开始手算
拿一个小输入，逐步手算
V=4，无向边 (0,1)、(0,2)。
| 操作 | graph[0] | graph[1] | graph[2] | graph[3] |
|---|---|---|---|---|
| 初始化 | [] | [] | [] | [] |
| 加入 0–1 | [1] | [0] | [] | [] |
| 加入 0–2 | [1,2] | [0] | [0] | [] |
| 统计 | 度数 2 | 度数 1 | 度数 1 | 度数 0 |
无向图中每条边在邻接表里记录两次，因此度数总和为 2E=4。节点 3 不可从 0 到达，但仍计入 V。
03把正确性的理由说清楚
表示必须与问题约定一致
- 先为每个合法节点建立一个独立列表，包含无邻居的节点。
- 每条无向边分别写入两端的邻接表，因此从任一端都能找到另一端；有向边则只写起点的列表。
- 后续算法遍历 graph[u] 时，恰好枚举题目允许从 u 直接走到的节点。建模若错了，遍历代码再正确也会回答另一个问题。
04把刚才的思路写成代码
基础课用 Python 表达，先对照变量含义与执行顺序。后续算法课提供 Python、C++ 与 JavaScript 三种实现。
def build_graph(n, edges):
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
return graph代码里的每个关键决定
graph = [[] for _ in range(n)]- 创建 n 个独立的邻接列表。不能写 [[]]*n，那会让所有位置引用同一个列表，修改一个节点时其他节点也一起改变。
graph[b].append(a)- 无向边要记录反方向；有向边应删除这一行。输入约定端点是 0 到 n−1 的合法整数。
return graph- 这只是建图，还没有执行 BFS、DFS 或求最短路。有权图可以把邻居记录为 (node, weight)，不要把权值误当成节点编号。
05这些操作要付出多少代价
把工作量具体数出来
建立 V 个空表需要 O(V)，处理 E 条边需要 O(E)，总时间 O(V+E)。
无向邻接表保存 V 个列表与 2E 个邻接项，空间 O(V+E)。邻接矩阵空间为 O(V²)。
遍历邻接表里的全部邻居项是 O(E)，但若每访问一个节点都重新扫描完整边列表，图搜索的复杂度就会变差。
06用一个反例检查理解
同一个空列表被复制了 V 次引用
若 graph=[[]]*4，执行 graph[0].append(1) 后，四个位置都会显示 [1]，因为它们实际引用同一个对象。这不是四个独立房间的邻居表。
怎样修正：使用列表推导式逐个创建列表。还要检查有向/无向约定和孤立节点，不能只凭画面看起来像一张图。
07自己推一次，再做自测
从数据还原一张图
V=4，无向边 (0,1)、(1,2)。写出邻接表，并回答从 0 能到达谁？如果边改成单向 0→1、1→2，从 2 还能回到 0 吗？
需要一点提示
分别为有向与无向情况写每个节点的出邻居。
查看完整推导与答案
- 无向邻接表为 [[1],[0,2],[1],[]]，从 0 可到 0、1、2，不能到 3。
- 有向邻接表为 [[1],[2],[],[]]，从 2 没有出边，不能回到 0。
- 边的方向改变可达性，不能把两种图交给同一个错误的建图过程。