图的表示与遍历
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| adjacency list/əˈdʒeɪsənsi lɪst/ | 邻接表 | lín jiē biǎo |
| adjacency matrix | 邻接矩阵 | lín jiē jǔ zhèn |
邻接表还是矩阵
- 图 $G = (V, E)$：课程图有 $V = \{A \ldots H\}$（$8$ 个节点）和 $10$ 条无向边。邻接表 adjacency list 按节点存邻居——$10$ 条无向边共 $20$ 条目；邻接矩阵 adjacency matrix 是 $8 \times 8$ 共 $64$ 格的网格，有边处为 $1$。
{exercise:uni-cs0505-storage}
练习
10 条无向边需要——条邻接表条目。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
每条无向边存两次，两端各一次。
为何是 O(V+E)
- 两种遍历都把每个节点标记一次（$V$ 的工作）、把每条存储的边扫一次（$E$ 的工作）：课程图上 $O(V+E)$。矩阵要付 $O(V^2)$，因为每行都要走完全部列，无论有没有边。
- 稀疏图（$E \ll V^2$）表胜；稠密图或只查一格时矩阵胜。记得标记已访问——真实图里有环，不标就死循环。
{exercise:uni-cs0505-cost}
练习
邻接矩阵上做 BFS 的代价是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
每行都走满 V 列，无论有无边——稀疏时表胜。
两种探测
- 从 $A$ 做 BFS（邻居按字母序）：层为 $A \,|\, B, C \,|\, D, E \,|\, F, G \,|\, H$；顺序读作 $A, B, C, D, E, F, G, H$，节点的层就是它到 $A$ 的最短跳数——队列让前沿按到达顺序离队。
- 从 $A$ 做 DFS：$A \to B \to D$；$D$ 的下一个未访邻居 $C$；$C \to E \to F \to H$；$H$ 的邻居 $G$ 收尾：$A, B, D, C, E, F, H, G$——纵深带回溯。BFS 答最短跳数；DFS 露出路径与环。
{exercise:uni-cs0505-orders}
练习
课程图上从 A 做 BFS 的顺序是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
队列逐层访问：A，然后 B C，再 D E，再 F G，最后 H。