🧠 高级算法：图算法 (9645)
你好！欢迎来到计算机科学中最强大且最令人兴奋的主题之一：图算法 (Graph Algorithms)。图不仅仅是条形图——它们是基础的数据结构，用于建模现实世界中复杂的联系，从社交网络到互联网映射，无处不在。
掌握这些算法意味着你可以找出回家的最短路线、解决逻辑谜题，并理解现代软件是如何在相互连接的数据中进行导航的。如果这些内容看起来有点复杂，请别担心；我们将通过清晰的类比，一步步拆解每个概念，帮助你牢固掌握！
1. 图的基本概念：构建结构
在对图运行算法之前，我们需要了解图究竟是什么以及它是如何构建的。
1.1 核心术语 (3.10.1)
图 (Graph) 是一种用于表示数据之间复杂关系的数据结构。
- 顶点 (Vertex) 或 节点 (Node)：表示关系中的实体或点。（可以想象成地图上的城市，或是社交网络中的用户。）
- 边 (Edge) 或 弧 (Arc)：表示两个顶点之间的连接或关系。（可以想象成连接两个城市的公路。）
图的类型
我们使用的算法类型通常取决于所处理的图的类型：
- 无向图 (Undirected Graph)：边没有方向。如果节点 A 与节点 B 相连，那么这种连接是双向的。（双向车道。）
- 有向图 (Directed Graph)：边具有明确的方向（即弧）。关系仅单向存在。（单行道，或者 Twitter 上的关注关系：我关注你，但你未必关注我。）
- 带权图 (Weighted Graph)：每条边都关联一个数值（“权重”）。该值通常代表成本、距离或时间。（道路的长度或航班的费用。）
快速回顾： 图算法通常关注两类任务：在节点间寻找路径，或者系统地遍历所有节点。
1.2 图的代码表示 (3.10.1)
在内存中，图通常使用两种主要结构来存储：
a) 邻接矩阵 (Adjacency Matrix)
这使用二维数组（矩阵）存储，行和列代表节点。如果节点 \(i\) 和节点 \(j\) 之间存在边，则 \([i][j]\) 处的位置会被标记（对于无权图通常标记为 1，对于带权图则标记为权重值）。
- 优点（何时使用矩阵）：
- 检查边是否存在非常容易（只需检查 \([i][j] = 1\) 是否成立）。这被称为频繁进行边存在性检查。
- 添加/删除边非常迅速。
- 最适合稠密图 (Dense Graphs)（相对于顶点数，边数很多的图）。
- 缺点：对于稀疏图 (Sparse Graphs)（边数很少的图），会浪费内存，因为矩阵中的大部分条目都是零。
b) 邻接表 (Adjacency List)
这使用列表或数组，其中每个索引代表一个节点。在每个索引处，都有一个链表（或数组/列表），其中包含该节点的邻居。
- 优点（何时使用列表）：
- 对于稀疏图更节省内存，因为你只存储现有的连接。
- 查找特定节点的所有邻居速度更快。
- 缺点：检查某个特定的边是否存在（从 A 到 B）需要遍历 A 的整个邻居列表，这可能比矩阵的直接查询更慢。
第 1 部分重点： 图通过边 (弧)连接节点 (顶点)。我们使用邻接矩阵进行快速的边检查和处理稠密图，而使用邻接表以在处理稀疏图时提高内存效率。
2. 搜索算法：广度优先搜索 (BFS) (3.11.1)
搜索算法用于系统地探索图。BFS 就像向池塘里扔一块石头——涟漪一层一层地向外扩散。
2.1 什么是广度优先搜索 (BFS)？
BFS 逐层或按广度探索图。它先找到起始节点的所有邻居，然后是邻居的邻居，以此类推，最后才深入图的更深处。
记忆窍门： Breadth-First（广度优先）采用 Broad（广泛的）方法，并使用 Queue（队列，先进先出）。
核心数据结构： BFS 使用队列 (Queue)（先进先出，FIFO）来管理下一步要访问的节点。这确保了距离起点较近的节点会被优先访问。
2.2 BFS 算法追踪（分步解析）
- 从指定的起始节点开始。标记为已访问，并将其加入队列。
- 当队列不为空时：
a. 出队 (Dequeue)（移除）第一个节点，将其称为当前节点。
b. 检查当前节点的所有未访问邻居。
c. 对于每个未访问的邻居，将其标记为已访问，并入队 (Enqueue)（加入）到队列中。 - 重复以上步骤直到队列为空。
你知道吗？ 由于 BFS 在移动到距离为 \(d+1\) 的节点之前，会系统地检查距离为 \(d\) 的所有节点，因此它本质上能找到无权图中的最短路径。这是你需要掌握的核心应用！
2.3 BFS 的应用 (3.11.1)
BFS 的典型应用是寻找无权图的最短路径。因为所有边的“权重”相同（为 1），算法可以保证当你第一次到达目标节点时，所经过的边数是最少的。
例子：查找社交网络中两个人之间的最少连接数。
BFS 重点： BFS 使用队列，按层探索，非常适合寻找无权图中的最短路径。
3. 搜索算法：深度优先搜索 (DFS) (3.11.1)
DFS 是一位坚定的探险家，它会沿着一条路径一直走到底，直到无路可走才回溯。
3.1 什么是深度优先搜索 (DFS)？
DFS 沿着图中的单一分支或路径进行探索，直到到达死胡同（即没有未访问邻居的节点）。然后它“回溯”到上一个交叉点并尝试下一条路径。
类比： 探索迷宫。你一直沿着一条通道走，直到撞墙，然后返回上一个路口，尝试下一条通道。
核心数据结构： DFS 使用栈 (Stack)（后进先出，LIFO）或递归 (Recursion)（利用调用栈）来管理回溯时需要返回的路径。
3.2 DFS 算法追踪（分步解析）
- 从指定的起始节点开始。标记为已访问并处理它。
- 如果当前节点有未访问的邻居：
a. 选择一个未访问的邻居，将其设为新的当前节点。（实际上是递归调用或压入栈中）。 - 如果当前节点没有未访问的邻居（死胡同）：
a. 回溯 (Backtrack)（返回）到上一个节点，并尝试从那里开始处理任何剩余的未访问邻居。 - 重复直到所有可到达的节点都被访问过。
实现： 你必须能够在代码中实现 BFS 和 DFS。在考试场景下，使用递归子程序来实现 DFS 通常是最简单的。
3.3 DFS 的应用 (3.11.1)
DFS 的典型应用是走迷宫或解决需要穷尽一个选项后再放弃的谜题。
例子：判断两点之间是否存在路径，或拓扑排序（根据依赖关系对任务进行排序）。
DFS 重点： DFS 使用栈（或递归），在回溯前深入探索单条路径，常用于迷宫导航和路径存在性检查。
4. 最短路径算法：Dijkstra 算法 (3.11.1)
BFS 非常适合无权图，但如果道路有不同的距离或成本呢？这时就需要用到 Dijkstra 算法。
4.1 Dijkstra 算法的目的
Dijkstra 算法用于在带权图中找到起始节点到所有其他节点的最短路径，前提是边的权重必须是非负的（距离或时间不能为负）。
类比： 这正是你的 GPS 在计算两点间最快路线时的做法——它考虑了每一条路（边）的权重（距离/时间）。
4.2 算法追踪（侧重理解）
除非题目中给出了步骤，否则你不需要背诵完整步骤或编写代码，但你必须能够追踪它。
追踪的核心思路涉及维护两组关键数据：
- 距离 (Distances)：一个列表，记录从起始节点到每个节点的已知最短距离。最初，起始节点的距离为 0，其他所有节点设为无穷大 (\(\infty\))。
- 已访问集 (Visited Set)：已确定从源点到该节点的最短距离的节点集合。
追踪过程（简化版）
- 初始化距离列表（起点 = 0，其他 = \(\infty\)）。
- 选择未访问节点中距离当前最小的一个（第一次即为起始节点）。
- 将所选节点标记为已访问（其最短路径现已确定）。
- 对于已访问节点的所有邻居，计算暂定距离（当前节点距离 + 边权重）。
- 如果这个暂定距离小于该邻居当前记录的距离，则更新距离为较小值。（此过程称为松弛 (Relaxation)）。
- 重复步骤 2-5，直到目标节点被访问，或者所有可达节点都已进入已访问集。
避免常见的错误： Dijkstra 只有在权重为非负时才能正确工作。如果权重可能是负数，则需要其他算法（如 Bellman-Ford），但这超出了本大纲的范畴。
4.3 最短路径算法的应用 (3.11.1)
任何需要在地图或网络中最小化成本、距离或时间的问题：
- 网络路由（数据包如何在互联网上高效传输）。
- 地理信息系统 (GIS) 和导航应用（如谷歌地图）。
- 调度与物流（寻找配送序列中最快路径）。
Dijkstra 重点： Dijkstra 算法通过不断更新和确认到每个节点的已知最短距离，找到带权图（且权重为非负）中的最短路径（追踪过程是关键技能）。
💡 高级算法总结表 (3.11.1)
| 算法 | 类型 | 核心数据结构 | 主要应用 |
|---|---|---|---|
| BFS | 搜索（广度优先） | 队列 (FIFO) | 无权图中的最短路径。 |
| DFS | 搜索（深度优先） | 栈 / 递归 (LIFO) | 走迷宫或检查连通性。 |
| Dijkstra | 最短路径 | 优先队列（隐式或迭代处理） | 带权图中的最短路径（非负权重）。 |