Algorithms on graphs

欢迎来到图论算法 (Algorithms on Graphs)！

在决策数学 1 (D1) 的这一章中，我们将学习如何使用“图”(Graphs，即点与线构成的网络) 来解决问题。你可以把它们想象成快递司机的路线图、网络电缆布局，甚至是社交媒体中的人际连接。

我们将重点探讨两个主要问题：
1. 最小生成树 (Minimum Spanning Trees, MST)： 如何用最少的“材料”（如电缆或道路）连接网络中的每一个点。
2. 最短路径 (Shortest Path)： 如何以最快或成本最低的方式，从 A 点到达 B 点。

如果刚开始觉得这些概念有点抽象，别担心！只要掌握了步骤，这其实就像跟着食谱做菜一样简单。

1. 最小生成树 (Minimum Spanning Trees, MST)

想象你正在铺设光纤电缆以连接五个村庄。你希望所有村庄都能接入网络，但电缆很贵，所以你想使用最小总长度。这就是最小生成树问题。

必须掌握的关键术语：

- 顶点 (Vertex / Node)： 图中的一个点（例如：村庄）。
- 边 (Edge / Arc)： 连接两个顶点的线（例如：电缆）。
- 权重 (Weight)： 分配给每条边的数字（例如：长度或成本）。
- 树 (Tree)： 一个连通且没有回路（没有环路）的图。
- 生成树 (Spanning Tree)： 一棵包含图中所有顶点的树。

Kruskal 算法 (Kruskal's Algorithm)

Kruskal 算法是以“边”为中心的算法。它的逻辑非常简单：只要不形成回路，就总是选择成本最低的边。

步骤：
1. 将图中所有的边按权重由小到大排列。
2. 检查权重最小的边。如果加入它不会产生回路（闭合环路），就选取它。
3. 接着看下一条权重最小的边，重复上述步骤。
4. 当所有顶点都连通时停止（对于 \(n\) 个顶点的图，你会得到 \(n-1\) 条边）。

小撇步： 如果一条边连接的两个点已经可以通过其他已选取的边互相到达，就舍弃它，因为加入它会形成回路！

Prim 算法 (图形版)

Prim 算法是以“顶点”为中心的算法。它像树木一样从起点开始向外生长。

步骤：
1. 随便选一个顶点作为起点（题目通常会指定起点）。
2. 检查所有与已选取顶点相连的边。
3. 选择连接到新顶点的最短边。
4. 重复步骤，直到所有顶点都进入你的树中。

类比： 想象一滩水从一个村庄开始流出，水流总是会沿着最短的路径流向邻近未湿的村庄。

Prim 算法 (矩阵版)

有时候，题目会给出一张数字表（距离矩阵）。Pearson Edexcel 经常要求你直接在这张表上执行 Prim 算法。

步骤：
1. 选择一个起始顶点。将该顶点的字段标记为“1”，并划掉该顶点对应的列。
2. 查看已标记的字段（即已在树中的顶点所在的字段）。
3. 在这些字段中，找出一个未被划掉的列中的最小数字。
4. 将该数字圈起来。该数字所在的列即为你的新顶点。
5. 将新顶点的字段标记为下一个顺序（2，然后是 3，以此类推），并划掉其对应的列。
6. 重复此步骤，直到所有列都被划掉。

常见错误： 忘记查看所有已标记的字段。在寻找下一个最小值时，你必须检查每一个顶部有编号的字段！

MST 重点总结：

Kruskal 算法需要先排序所有的边。Prim 算法则是一次增加一个顶点来构建树。两者最终都会得到相同的最小总权重！

2. Dijkstra 算法 (最短路径)

如果说 MST 是为了连接“所有人”，那么 Dijkstra 算法就是找出从特定起点到特定终点的最短路径。这正是 Google 地图或汽车导航计算路线的原理。

运作方式：

每个顶点都有一个“标签框”。在 D1 中，这个框通常分为三部分：
1. 顶点名称。
2. 标记顺序（何时变为“永久”标签）。
3. 最终（永久）标签（从起点出发的最短距离）。

框内还有空间用于记录临时标签（我们目前正在测试的距离）。

步骤流程：

1. 起点： 给起点赋予永久标签 \(0\)。标记它是第 1 个被固定的顶点。
2. 更新： 查看所有与刚刚被设为永久的顶点直接相连的顶点。
3. 计算： 对于每个相邻顶点，将该边的权重加上你当前顶点的永久标签值，写入该邻点的临时标签区。
4. 选择： 观察整个图中所有的临时标签，找到最小的一个。
5. 永久化： 将该最小的临时标签变为永久，并标记其顺序（第 2 个、第 3 个等）。
6. 重复： 以刚刚设为永久的顶点作为起点，回到第 2 步。继续进行直到目标顶点获得永久标签为止。

你知道吗？ Dijkstra 算法是“贪婪”的。它总是选择当下看起来最近的选项，相信这就是迈向最终目标的最佳步骤。

寻找实际路径：

得到数字后，如何确定该走哪条路？你需要从终点倒推回去！

规则： 如果顶点 \(B\) 与顶点 \(A\) 相连，且：
\((\text{B 的永久标签}) - (\text{边 AB 的权重}) = (\text{A 的永久标签})\)
...那么边 \(AB\) 就是最短路径的一部分！

刚开始觉得复杂别担心： 最重要的是保持整洁。如果你的“临时标签”写得很乱，可能会选错下一个永久标签的数字。

速查表：

Dijkstra 算法
- 起点： 标记 \(0\)。
- 计算： 将边权重与当前的永久标签相加。
- 选择： 总是选取所有临时标签中的全局最小值作为下一个永久标签。
- 回溯： 最后利用标签来找出路径。

3. 总结与成功秘诀

避免常见错误：

- 在 Kruskal 中： 不小心包含了一条会形成回路的边。在加入新边之前，务必再次检查两个点是否已经连通。
- 在 Prim (矩阵) 中： 忘记划掉新顶点的列。这会导致你重复选取同一个已经访问过的顶点。
- 在 Dijkstra 中： 忘记更新临时标签。如果你在过程中发现了某个顶点的更小临时距离，一定要用新的、更小的数值取代旧的临时标签。

记忆法：

- Kruskal's Keeps edges in order (K 代表 Kruskal 和 Keep 排序)。
- Prim's Picks a starting vertex (P 代表 Prim's 和 Point 起始点)。
- Dijkstra is for Distance between two points (D 代表 Dijkstra 和 Distance 两点间距离)。

本章要点：

图论算法是合乎逻辑的步骤流程。在考试中，评分员主要看你是否有清晰的步骤证据。务必展示 Kruskal 的排序列表、Prim 矩阵的标记顺序，以及 Dijkstra 的所有临时标签。即使最终答案有轻微偏差，只要你展示了正确执行算法的过程，依然可以拿到大部分分数！