图的表示

图的表示把顶点和边转换成可存储、可查询的数据。邻接表为每个顶点保存一行邻居，空间为 O(V + E)。邻接矩阵分配 V × V 个格子，空间为 O(V²)，用一次索引读取回答 has_edge(u, v)。

邻接表像通讯录，打开 u 只看它已有的邻居。矩阵为每对顶点预留位置，包括没有边的组合。它用额外空间换取固定位置查询。

空间与查询速度的取舍

本课使用简单无向图：没有重边，也没有自环。边 u-v 没有方向，两种表示都必须对称存储。

邻接表对一条边执行两次追加：把 v 放入 adj[u]，把 u 放入 adj[v]。所以 E 条无向边产生 2E 个邻居条目，另有 V 个行入口。

矩阵则写入 matrix[u][v] = 1 和 matrix[v][u] = 1，两格关于主对角线对称。0 表示无边；本课不允许自环，所以对角线保持 0。

对称性是不变量。邻接表保存两个方向、矩阵只写一格时，两者描述的图就不同。表只追加一个方向，则变成了有向关系。

邻接表可用 len(adj[u]) 读取度数；检查边是否存在，要在该行寻找 v。矩阵检查边只读 matrix[u][v]，计算度数却要对整行求和。

逐步演示

默认有顶点 0 到 5，按顺序加入五条边：0-1、0-2、1-3、2-3、3-4。顶点 5 保持孤立，仍需要自己的存储行。

1. 建立六个空邻接行和全为 0 的 6 × 6 矩阵。
2. 编码 0-1：adj[0] 追加 1，adj[1] 追加 0；矩阵 [0][1]、[1][0] 写为 1。
3. 编码 0-2：在 adj[0]、adj[2] 加入对应邻居，矩阵 [0][2]、[2][0] 写为 1。
4. 对 1-3、2-3、3-4 重复双向写入。没有写入顶点 5 的邻居。
5. 邻接表为 0:[1,2]、1:[0,3]、2:[0,3]、3:[1,2,4]、4:[3]、5:[]。共十个条目，即 2E = 10。
6. 矩阵有 V² = 6² = 36 格。顶点 3 的行是 [0,1,1,0,1,0]，对应邻居 1、2、4。
7. 求 degree(3)：表读取 len(adj[3]) = 3；矩阵检查六格并求和，也得 3。
8. 求 has_edge(3, 5)：表依次比较 1、2、4 与 5，三次探测后行结束，返回 False。
9. 矩阵只读 matrix[3][5] = 0，一次查询返回同样的 False。

画布在编码时保留源边，并点亮表中的两项和矩阵的对称格。查询时，表的游标逐个移动，矩阵的引导线只交于一格，展示两种查询成本。

时间与空间复杂度

V 为顶点数，E 为无向边数，degree(u) 为 u 的邻居数。

这里的加边成本对应有效、无重复的输入，不包含额外查重。频繁查询任意两点是否相连时，矩阵的空间可能值得付出；主要遍历已有邻居时，表避免扫描大量 0。

稀疏图的 E 远小于 V²。默认图只需六个行入口、十个邻居项，而矩阵预留 36 格。

Dense K5 展示稠密图：五个顶点、十条边，表的逻辑项数为 V + 2E = 5 + 20 = 25，矩阵也是 V² = 25。这不是字节比较，各结构的对象和指针开销不同；它说明当 E = Θ(V²) 时，邻接表不再有渐近空间优势。

边界情况

• 单顶点图：邻接行为空，1 × 1 矩阵为 0，degree(0) = 0。
• 孤立顶点：默认顶点 5 没有邻居，但表行和矩阵行都存在。
• 不存在的边：has_edge(3, 5) 返回 False 是正常结果。
• 稠密图：Dense K5 中，表的后部命中可能扫描四个邻居，也失去稀疏空间优势。
• 自环与重边：本课不支持；扩展时必须规定对角线和重复邻居项的含义。

常见错误

• 邻接表只写一个方向。 无向边要求 adj[u]、adj[v] 同时更新。
• 矩阵只写一格。 [u][v] 与 [v][u] 必须相同。
• 把矩阵空间说成 O(E)。 即使多数位置为 0，也分配 V² 格。
• 把表的单次边查询算成扫描全图。 它只扫描 adj[u]，边界是 O(degree(u))，不是直接写 O(V + E)。
• 把逻辑项数当字节数。 V + 2E 与 V² 表示增长关系，不表示每项占相同内存。