图
图由顶点和边组成，适合表达连接、依赖和状态转换。选择算法前，应先确定方向、权重与状态的身份；同一业务可以因建模方式不同而产生不同的图。
1. 面试核心
先记住这几条，再读正文- 邻接表占用 O(V+E) 空间，邻接矩阵占用 O(V²) 空间。
- 普通 BFS 在边成本相同时求最少边数路径；DFS 常用于可达性和完整遍历。
- 有环图需要访问标记，非连通图需要从多个未访问顶点开始。
2. 顶点、方向与权重
“课程 A 是 B 的前置”可表示为 A → B；“城市之间有道路”可能需要无向边或两条方向不同的边。若道路长度不同，最少经过道路数不等于总距离最短。
0: [1, 2]
1: [2]
2: []
这是一个有向邻接表，表示 0→1、0→2、1→2。判断 0 是否直接连接 2 需要检查 0 的邻居；矩阵可以 O(1) 判断某条边是否存在，但无论边多少都需保存 V² 个位置。
3. 搜索与访问状态
邻接表完整 DFS/BFS 读取每个顶点和每条边有限次，时间 O(V+E)。对矩阵逐行寻找邻居时，时间通常为 O(V²)。无向边可能存储两次，这不会改变渐近复杂度。
图中 0→1→2→0 构成环。不标记访问过的顶点会反复扩展。BFS 通常在入队时标记，避免同一顶点被多个前驱重复加入。实现及层次推导见树与图搜索。
4. 使用边界
只从一个起点搜索只能覆盖其可达部分。统计全图连通分量时，要遍历顶点集合，对未访问顶点再次搜索。网格、字符串变换等隐式图还需明确合法邻居与状态判等方法。
带权最短路、拓扑排序、路径枚举各有额外约束。特别是“全局已访问”适合可达性搜索，但枚举不同路径时可能需要仅标记当前路径并在回退时撤销，否则会误删合法答案。
5 · 面试题卡片
先想答案，再翻面题目来自公开面经。点任意一张进入翻卡，可左右切换，看完回到这里。
逐张翻看 1 张 →5.1 邻接表和邻接矩阵如何选择，复杂度有什么区别？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：图的稀疏程度、边查询成本与邻居遍历成本。
参考回答
稀疏图通常用邻接表，空间 O(V+E)，遍历邻居与实际边数相关。矩阵占 O(V²)，但直接查询两个顶点间是否有边是 O(1)，适合规模较小且频繁查边的情况。完整搜索在邻接表上通常 O(V+E)，矩阵上找邻居通常需要 O(V²)。