Algorithms on graphs

欢迎来到图算法（Graph Algorithms）的世界！

在决策数学 1 (Decision Mathematics 1, D1) 的这一章中，我们将学习如何利用图（Graphs）（即网络）来解决现实世界中的问题。想象你是一位工程师，需要用最少的材料将多个城镇连接起来；或者你是一位送货司机，正在寻找两座城市之间绝对最短的路线。这些绝非猜谜游戏——我们使用称为算法（Algorithms）的特定、分步骤的规则，来确保每次都能找到完美的答案。

如果起初觉得这些概念有点抽象，请不用担心。我们会将所有内容拆解成简单的步骤，使用你熟悉的类比，并指出学生常犯的“陷阱”。让我们开始吧！

1. 最小生成树（“最小连接”问题）

想象你有一组岛屿，你想用桥梁将它们连接起来。为了节省成本，你希望桥梁的总长度最小，但必须确保每个岛屿都能连接到网络中。这就是所谓的最小生成树 (Minimum Spanning Tree, MST)。

你需要了解的关键术语：
• 顶点 (Vertex / Node)： 图上的一个点（例如城镇或岛屿）。
• 边 (Edge / Arc)： 连接两个顶点的线段。
• 权重 (Weight)： 边上的数值（代表距离、成本或时间）。
• 树 (Tree)： 一个连通且没有圈（即没有回路）的图。
• 生成树 (Spanning Tree)： 一棵连接图中所有顶点的树。

寻找 MST 有两种主要算法：克鲁斯卡尔算法 (Kruskal’s Algorithm) 和 普里姆算法 (Prim’s Algorithm)。

克鲁斯卡尔算法 (Kruskal’s Algorithm)

Kruskal 算法就像是一位精打细算的猎人。只要不形成回路，你总是优先选择最便宜的“交易”（边）。

操作步骤：
1. 将图中所有的边按大小（从小到大）列出。
2. 从整个图中最短的边开始；将它加入你的树中。
3. 选择下一条最短的边。将它加入，除非它会形成一个圈（cycle）（即闭合回路）。如果会形成回路，就把它舍弃！
4. 重复上述步骤直到所有顶点都连接起来。对于有 \(n\) 个顶点的图，你将需要刚好 \(n - 1\) 条边。

避免常见错误： 学生经常忘记检查是否有圈。请务必问自己：“如果我加上这条边，我能绕成一个圈吗？”如果答案是肯定的，就不要加上那条边！

普里姆算法 (Prim’s Algorithm)

Prim 算法则不同，它像树木一样从一个起点开始“生长”。你总是寻找离你当前网络最近的邻居。

操作步骤（在图上）：
1. 选择任意一个顶点作为起点（通常题目会指定）。
2. 查看所有连接“已开始”顶点和“未开始”顶点的边。选择其中最短的一条。
3. 将该新顶点加入你的集合。现在，检查所有连接你已连接的顶点到新顶点的边。
4. 重复直到所有顶点都被包含在内。

在距离矩阵（Distance Matrix）上使用 Prim 算法：
在考试中，你经常会被要求使用表格（矩阵）来执行 Prim 算法。这是 Pearson Edexcel 课程大纲中非常常见的要求。
1. 选择一个起始顶点，并在其对应列的上方标记为 "1"。
2. 划掉该顶点的行。
3. 查看已标记列中的数值（例如第 1 列）。圈出最小的可用数值。
4. 该数值所对应的行所代表的顶点，就是你的下一个顶点。将其列标记为 "2"，划掉其行，然后重复步骤。

快速复习箱：
• Kruskal 算法： 从全图最短边开始。顺序不重要，但严禁形成回路。
• Prim 算法： 从一个顶点开始。从已连接的网络中逐步扩展。

2. 戴克斯特拉算法 (Dijkstra’s Algorithm)（最短路径）

虽然 MST 是为了以最低成本连接所有人，但 Dijkstra 算法是用于寻找从一个特定起点到另一个特定目的地之间的最短路径。可以把它想作是 GPS 或 Google 地图背后的逻辑。

工作框（Working Box）：
在考试中，你会在每个顶点看到一个“框”。它看起来像这样：
\( [ \text{标记顺序} \mid \text{最终标签} \mid \text{运算数值} ] \)

操作步骤：
1. 开始： 将起始顶点的最终标签设为 0。标记顺序为 1。
2. 更新： 查看所有与你刚设为“永久”的顶点相连的顶点。计算从起点到这些邻居的距离。将结果写在“运算数值”部分。
3. 选择： 查看整张图上所有临时运算数值。选出最小的一个。这就是你的新“永久”顶点。
4. 定案： 为它分配下一个“标记顺序”及其“最终标签”（距离）。
5. 重复： 继续进行，直到目的地顶点获得最终标签。

类比： 想象水从起点开始淹没迷宫。“最终标签”就是水第一次到达该特定交叉口的时间。

如何找出实际路径：
一旦获得最终标签，请从目的地倒着推回去。如果符合以下条件，则顶点 \(B\) 在从 \(A\) 到目的地的路径上：
\( (\text{B 的最终标签}) - (\text{A 的最终标签}) = \text{边 } AB \text{ 的权重} \)

避免常见错误： 在选择下一个永久顶点时，必须查看整张图上所有的临时标签，而不仅仅是当前顶点旁边的标签！

总结与重点提示

你知道吗？
“最小连接”问题最初是由科学家在 1920 年代试图设计高效电力网时解决的。今天，同样的数学原理被 Netflix 等公司使用，以确保数据能快速传送到你的屏幕上！

期末复习：
• 如果你有一份所有边的列表并且想避免形成回路，请使用 Kruskal 算法。
• 如果你从特定顶点开始，或者正在处理矩阵/表格，请使用 Prim 算法。
• 如果你需要找出从 A 点到 B 点的最短路径，请使用 Dijkstra 算法。
• 在 Dijkstra 算法中，务必显示你的运算数值——即使你把它们划掉了。考官需要看到你在纸上的“思考过程”！

如果起初觉得这些很棘手，请别担心！ 掌握这些算法的最佳方法就是练习绘制图表并填写表格。一旦你找到了步骤的节奏，这就变成了一个你每次都能完美解开的谜题。