知识点深化 · 数据结构 · 图基础
图基础与遍历：邻接表/邻接矩阵、BFS/DFS
图由顶点和边组成，表达"谁和谁有关系"——地图导航、社交网络、推荐系统都是图。存储有邻接矩阵和邻接表两种；遍历有 BFS（广度，用队列）和 DFS（深度，用栈/递归）。这一页把图的表示和两种遍历讲透。
① 小白第一课怎么学（4 步走，约 60 分钟）
别急着背代码，先按这四步建立直觉：
1看图建立直觉（10 分钟）
读②③：把图想成城市和道路。
2记存储与遍历（15 分钟）
读④：邻接表/矩阵，BFS/DFS 模板。
3手推遍历（20 分钟）
精读⑤：给邻接表跑一遍 BFS 和 DFS。
4刷题纠错（15 分钟）
做⑦⑩，错题回⑥。
本课小目标学完你要能：① 画出邻接表和邻接矩阵；② 说清 BFS/DFS 区别；③ 用 BFS 求最短路径（无权）。
② 一图看懂：图与遍历全地图
读法：中心是图，左存储方式右遍历方式，下是应用与易错。
③ 本质直觉：图就是城市地图，BFS 一层层扩，DFS 一条路走到底
图 G=(V,E)：V 是顶点集合（城市），E 是边集合（道路）。边可以有方向（单向路）也可以无方向（双向路），还能带权（距离）。
两种存储：邻接表——每个顶点存一个邻居链表，省空间，稀疏图常用；邻接矩阵——n×n 矩阵存是否有边，查边 O(1) 但占 O(n²)，稠密图用。
BFS：从起点出发，先访问距离 1 的所有点，再距离 2……像水波扩散。用队列。无权图里 BFS 第一次到终点就是最短路径。DFS：一条路走到黑，走不通再回头，用栈/递归。
为什么必须 visited图里有环，不标记访问过的顶点会无限绕圈。每次访问一个点就标记，再次遇到直接跳过。
④ 完整体系与对比表
存储方式对比
| 对比 | 邻接表 | 邻接矩阵 |
|---|
| 空间 | O(V+E) | O(V²) |
| 查 u→v 边 | O(deg(u)) | O(1) |
| 适合 | 稀疏图（边少） | 稠密图（边多） |
| 典型 | 社交网络 | 小型稠密图 |
BFS 模板
BFS（队列 + visited）queue.push(start); visited[start]=true;
while(q 非空){ u=q.pop(); for(v in u 的邻居) if(!visited[v]){ visited[v]=true; q.push(v);} }
DFS 模板
DFS（递归）dfs(u){ visited[u]=true; for(v in 邻居) if(!visited[v]) dfs(v); }
无权图 BFS 第一次到达目标就是最短路径（边数最少）；DFS 不一定最短，但能探全部连通。
⑤ 用法场景与典型例题
例1（邻接表）A 连 B、C；B 连 D；C 连 D，从 A 的 BFS 顺序？
队列逐层扩展。
① 出 A，入 B、C；② 出 B，入 D；③ 出 C，D 已访问跳过；④ 出 D。答案：A B C D。
例2（最短路径）无权图 A→B→D 两步，A→C→D 两步，A 到 D 最短路长？
BFS 按层，第一次到 D 的层数。
距离 1：B、C；距离 2：D。答案：2 条边。
例3（连通）5 个顶点的图，DFS/BFS 访问的顶点数等于？
能访问到的连通分量大小。
从起点出发能到达的所有顶点构成一个连通分量；若图不连通，需对每个未访问顶点重启 DFS。
做题心法无权最短路想 BFS；要"能否到达/全部探索"想 DFS。遍历必带 visited 数组。
⑥ 高频错误诊断（4 条）
错误1：忘了 visited 导致死循环有环图不标记 visited，会无限绕。每个点访问一次就打标记。
错误2：混淆 BFS 和 DFS 的结构BFS 用队列 FIFO 逐层；DFS 用栈/递归一条路到底。别用错。
错误3：邻接矩阵存稀疏图浪费n=1万 时矩阵要 1亿 格，稀疏图该用邻接表。
错误4：以为 DFS 最短路DFS 一条道走到黑不保证最短；无权最短路要用 BFS。
⑦ 考点真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 存储选型 | 稀疏图用什么 | 邻接表 O(V+E) |
| BFS/DFS 结构 | 各用什么 | BFS 队列，DFS 栈/递归 |
| 无权最短路 | 用哪个遍历 | BFS |
| 防环 | 遍历必带什么 | visited 数组 |
真题基础1. BFS 广度优先遍历使用的数据结构是？
真题中档2. 稀疏图（顶点多、边少）最省空间的存储方式是？
真题中档3. 无权图中求两点间最短路径（边数最少）应使用？
真题拔高4. 图遍历为什么必须维护 visited？
⑧ 必背知识点卡
图：顶点 V + 边 E 有向/无向/带权
邻接表：存邻居链表，O(V+E) 稀疏图
邻接矩阵：n×n，查边 O(1) 稠密图 O(V²)
BFS：队列逐层，无权最短路 visited
DFS：栈/递归，探到底 连通分量
防环：访问过就标记 别重复
应用：导航/社交/拓扑排序
⑨ 应用输出：实现地图两点间最短公交站数
场景：城市地铁站图，问从 A 站到 B 站最少坐几站。
① 建模：地铁站是顶点，相邻线路连通是边（无权）。
② 选型：求最少站数 = 无权最短路，用 BFS。
③ 遍历：从 A 入队，逐层扩展邻居，记录每点距离=父点距离+1。
④ 命中：第一次弹出 B 时，其距离就是最少站数。
⑤ 还原路径：BFS 时记录每个点的前驱，从 B 回溯到 A。
口述思路合上书说："最少站数就是 BFS 按层扩散，第一次到终点的层数即答案。"
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础5遍历图为什么要 visited？
防止有环时死循环。
基础6无权图最短路用 BFS 还是 DFS？
BFS。
▍中档 6 题
中档9BFS 第一层是什么？
起点的直接邻居（距离 1）。
中档10DFS 递归深度过深会怎样？
栈溢出，改迭代栈。
中档11怎么判断图是否连通？
从任一点 DFS/BFS，访问到全部顶点则连通。
中档12拓扑排序用什么遍历？
DFS 后序逆序，或 BFS Kahn 算法。
▍拔高 6 题
拔高13Dijkstra 求带权最短路和 BFS 区别？
带权不能 BFS，要优先队列每次取最近点（贪心）。
拔高14如何判断有向图有环？
DFS 看是否回边（在栈中的灰点），或拓扑排序能否排完。
拔高15BFS 如何记录路径？
每访问一个点记录其前驱 parent，结束后回溯。
拔高16双向 BFS 优势？
从起点和终点同时 BFS，相遇即停，指数级减少搜索量。
拔高17并查集解决什么图问题？
动态判断连通性、Kruskal 最小生成树。
拔高18邻接表如何存带权边？
邻居节点里同时存 (邻接点, 权重)。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 图是点和边，稀疏用邻接表稠密用矩阵。② BFS 队列逐层最短路，DFS 栈递归探到底。③ 遍历必带 visited，有环不死循环。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画邻接表和 BFS | 能写出队列过程 |
| 第 2 天 | 背存储对比 + 基础 1-6 | 空间复杂度对 |
| 第 3 天 | 做中档 7-12，手推 BFS 顺序 | 逐层正确 |
| 第 4 天 | 做拔高 13-18，理解 Dijkstra | 能讲清与 BFS 区别 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述口诀，默写 BFS 模板 | 不看资料全默对 |
← 返回软件技术总览