欢迎来到图遍历（Graph Traversal）的世界！

在本章中，我们将学习计算机如何“走遍”一个图（graph）来寻找信息。无论是 Google 地图帮你找出前往最爱披萨店的最快路线，还是 Facebook 向你推荐新朋友，图遍历算法都是实现这些功能的幕后功臣。

如果一开始觉得图看起来有点杂乱，别担心——看完这些笔记后，你就会发现它们其实就是等待被破解的逻辑谜题！

先修知识：什么是图（Graph）？

在我们进行“遍历”（Traverse，其实就是“访问”的高级说法）之前，先来复习一下图的组成：

  • 顶点（Vertices 或 Nodes）： 图中的点或“圆圈”（就像地图上的城市）。
  • 边（Edges 或 Arcs）： 连接节点的线（就像城市之间的道路）。

1. 广度优先搜索（Breadth-First Search，简称 BFS）

你可以把 广度优先搜索 想象成“池塘里的涟漪”。你从一个点出发，先探索所有最近的邻居，然后再扩散到下一层，以此类推。

“逐层推进”策略

BFS 采用 逐层（layer by layer） 方式探索图。你会先访问距离为 1 的所有节点，接着是距离为 2 的所有节点，等等。为了记录接下来要访问哪些节点，BFS 会使用 队列（Queue） 数据结构（先进先出，First-In, First-Out）。

步骤详解：

1. 选择一个起始节点，并将其标记为 已访问（visited）。
2. 将所有 直接相邻的邻居 加入 队列（Queue）。
3. 从队列中取出第一个节点。
4. 如果该节点尚未被访问，则将其标记为已访问，并将 该节点的所有邻居 加入队列的末端。
5. 重复以上步骤，直到队列为空。

现实生活中的比喻：社交媒体搜索

想象你在 LinkedIn 上搜索某人。首先，你会查看你的 直接联系人（距离为 1）。如果找不到，你再查看 联系人的联系人（距离为 2）。这就是先“广泛”地搜索，再深入探索。

典型应用：最短路径

由于 BFS 会优先探索邻近的节点，它是寻找 无权图（unweighted graph）（即每条路长度都一样的图）中 最短路径 的绝佳工具。它能保证当你找到目标时，所经过的边数是最少的。

重点速记：BFS
  • 数据结构： 使用 队列（Queue）。
  • 搜索风格： 广阔/宽度。
  • 最佳用途： 寻找 最短路径。

2. 深度优先搜索（Depth-First Search，简称 DFS）

如果说 BFS 像涟漪，那么 深度优先搜索 就好比一个在黑暗洞穴中探险的探险家。你会选择一条路一直走到底，直到遇到死胡同，然后 回溯（backtrack） 到上一个分岔路口，再尝试另一条路。

“深入探索”策略

DFS 会在移动到下一条分支前，彻底探索当前的一条分支。为了管理此过程，DFS 使用 栈（Stack） 数据结构（后进先出，Last-In, First-Out）或 递归（Recursion）。

步骤详解：

1. 选择一个起始节点，并将其标记为 已访问（visited）。
2. 移动到一个 尚未访问的相邻邻居。
3. 重复步骤 2，直到到达一个没有未访问邻居的节点（死胡同）。
4. 回溯（Backtrack） 到前一个节点，并检查是否有其他未访问的邻居。
5. 当你回溯到起点且所有节点都已访问完毕时，过程结束。

现实生活中的比喻：走出迷宫

AQA 课程大纲中提到的 走迷宫 是 DFS 最经典的应用。你在走廊里一直往前走直到撞墙，然后回头尝试刚才经过的分岔路口。你不会同时尝试所有的走廊，而是先走完一条路。

典型应用：迷宫求解与游戏逻辑

DFS 非常适合用于 迷宫导航 或那些需要判断长路径尽头是否有解的谜题。它比 BFS 使用更少的内存，因为它只需要记录当前路径上的节点。

重点速记：DFS
  • 数据结构： 使用 栈（Stack）（或递归）。
  • 搜索风格： 深度。
  • 最佳用途： 走迷宫。

比较 BFS 与 DFS

考试中很常要求你在两者之间做出选择。以下是一个记住两者区别的简单方法：

记忆小技巧：字母法
- BFS = Breadth（广度，向“宽”处搜索）
- DFS = Depth（深度，向“深”处搜索）

常见陷阱：

  • 忘了标记节点： 如果你不将节点标记为“已访问”，计算机可能会绕圈圈陷入死循环（无限循环）！
  • 队列 vs. 栈： 学生常会搞混这两个。记住：BFS 用 Queue（排队等候以便进行广度扩张），DFS 用 Stack（把路径堆叠起来以便深入探索）。

总结

图遍历 是许多复杂算法的基础。请为你的 AQA 考试记住这两大重点：

1. 广度优先搜索 (BFS) 使用 队列 (Queue)，透过优先检查所有邻居来寻找 无权图中的最短路径。

2. 深度优先搜索 (DFS) 使用 栈 (Stack)，将路径探索到底，是 迷宫导航 的经典方法。

如果刚开始追踪这些步骤觉得很慢，别担心。拿张纸和笔，画几个节点，试着用队列或栈实际“走”一遍。你很快就会领悟其中的窍门！