图的遍历与最短路：BFS、DFS、Dijkstra 各自能回答什么
一张图，三种答案
先把输入钉死，后面所有数字都来自这一份输入。在演示台的图输入框里填：
A-B, A-C, B-D, C-D, C-E, D-F, E-F, F-G
7 个顶点、8 条边，不带权，起点 A。同一份输入分别跑 BFS 和 DFS 演示页：
| 算法 | 访问顺序 | 演示帧数 |
|---|---|---|
| BFS | A → B → C → D → E → F → G | 26 |
| DFS | A → B → D → C → E → F → G | 38 |
帧数不同是因为 DFS 多出来的是回退和重复检查邻居的步子。但访问顺序本身不是重点，重点是这两种顺序各自能让你数出什么。
BFS 能数出来的是「层数」
BFS 的队列把当前顶点没标记的邻居按名称顺序放进去，先放的先出来，所以它天然按「离起点几条边」分层。在这张图上，BFS 给出的层数是：A=0、B=1、C=1、D=2、E=2、F=3、G=4，最深 4 层。
这个层数就是不带权图上 A 到各点的最少边数。自己在演示台上数的方法：单步前进，每出队一个顶点就记下它新标记了哪些邻居，数它是第几层被标记的，而不是数它是第几个被访问的。演示页写明的性质是「BFS 第一次到达某个顶点时走的边数就是最短的」，前提是不带权的图。
演示页还提醒两件事：邻居的处理顺序会影响访问顺序，但不影响每个顶点离起点的层数；在入队时就打标记比出队时才打标记省事，后者同一个顶点可能被多次放进队列。
DFS 给的是一条走得通的路
DFS 沿一条边一直往下钻，钻不动了才回退。同一张图上，它首次到达各顶点时的递归深度是：A=0、B=1、D=2、C=3、E=4、F=5、G=6。
把两组数字并排看，结论直接就出来了：C 和 A 之间明明只隔着一条边 A-C，BFS 在第 1 层就到 C，DFS 却把它排到第 3 步才到达；F 离 A 最少 3 条边，DFS 走了 5 层。DFS 输出的是可行路径，不是最短路径——它证明的是「从 A 能走到那儿」，不是「这么走最近」。
所以 DFS 的用武之地不在这里：连通块、判断有没有环、拓扑排序都建立在它身上。演示页也提醒，图很大时递归层数可能超过语言的调用栈上限，那时要改用显式栈；这次实测的 7 个顶点里最深到 6 层，还在栈里跑得动。
边数最少不等于权重最小
下面换另一张图（带权，6 个顶点、9 条边），不要和上图的结论混着看：
A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, C-E:10, D-E:2, D-F:6, E-F:3
BFS 只数经过了几条边，不看权重，所以在带权图上它回答不了「最省」的问题。反例图 A-B, B-C, C-D, A-D（4 个顶点）里，BFS 从 A 出发的访问顺序是 A → B → D → C；按边数算，A 到 D 只要 1 条边，但给 A-D 加上权 10 之后，这条「最短」路的权重可能远大于别的路。
Dijkstra 回答的是权重和最小
同一张带权图上，从 A 出发，Dijkstra 给出：
| 顶点 | 最短距离 | 一条最短路径 |
|---|---|---|
| A | 0 | A |
| B | 3 | A → C → B |
| C | 2 | A → C |
| D | 8 | A → C → B → D |
| E | 10 | A → C → B → D → E |
| F | 13 | A → C → B → D → E → F |
两处值得对着数：E 有两条入边，C-E 权 10 和 D-E 权 2，Dijkstra 选了 D-E，于是 E 的最短距离是 10；换走 C-E 这条边数更少的路，单是 C-E 的权重 10 就已经追平 E 的最短距离，再加上前面 A-C 的 2 只会更贵。D 也一样，C-D 权 8 和 B-D 权 5，选了 B-D，D 的最短距离是 8；走 C-D 虽然少一条边，但要经过权重 8 的 C-D 再叠上 A-C 的 2，比走 B-D 的 5 更重。边数更少那条反而更贵——这就是「最少步数」和「权重最小」的分界线。
它凭什么敢把一个顶点的距离定死：所有边权非负时，从已确定区域往外走只会让距离变大，当前最小的 dist 不可能再被别的路径改小。这也解释了非负权这个前提——有负权边时，已经「确定」的顶点之后还可能被改小，结果会出错，演示台遇到负权会直接拒绝。路径则是靠 prev 数组记下每个顶点是从谁更新来的，倒着追回去就是表格里那一列。
邻接矩阵还是邻接表
| 邻接表 | 邻接矩阵 | |
|---|---|---|
| BFS / DFS | O(V + E)，每个顶点入队出队一次，每条边从两端各看一次 | O(V²)，每行都要扫整行 |
| Dijkstra | 用二叉堆维护待定顶点可到 O((V + E) log V) | 每轮扫全部顶点找最小值、共 V 轮，O(V²)，适合稠密图 |
| 算法额外空间 | O(V) | O(V) |
取舍就在 E 和 V² 的差距上：E 接近 V² 时，为矩阵多付的代价本来也省不掉；E 远小于 V² 时，邻接表按实际存在的边走一遍就够了。
怎么自己在演示台试
- 图输入框里不带权的边写
A-B，带权的边写成A-B:4，顶点名会按名称顺序处理邻居。 - 演示台的图最多 10 个顶点、20 条边，超了会被拒绝，分组测就行。
- 同一份输入分别开 BFS 页和 DFS 页，用前进后退键对齐到「某顶点第一次被到达」那一帧，对比层数和递归深度。
- 想亲手让 BFS 在带权图上失手，就造一条边数少但权重大的路（比如上面那张 4 顶点反例图），再给它加权。
- 在 Dijkstra 页试着把某条边改成负权，看演示台怎么拒绝你，比读前提有效得多。