欢迎来到图论算法！
在决策数学 1 (Decision Mathematics 1) 的这一章中，我们将从图论的基本定义迈向精彩的算法 (algorithms) 世界。算法本质上就是用来解决特定问题的一步步指令。
为什么这很重要？因为无论是你使用 GPS 规划回家最快的路径，还是公司试图以最少材料铺设光纤电缆，背后使用的正是这些数学工具！
如果起初觉得步骤很多，不用担心——把它们想象成食谱就好。只要按顺序执行这些步骤，你每次都能得到正确的结果。
1. 最小生成树 (Minimum Spanning Trees, MST)
想象你要将多个住户连接到主水管。你希望每个住户都能接通，但为了节省开支，你想使用总长度最短的管线。这就是最小生成树问题。
生成树 (Spanning Tree) 是一个子图，它包含了原图中的每一个顶点 (vertex)，但没有回路 (cycle)（它看起来像一棵“树”）。而最小生成树就是所有边的权重总和为最小的那一个。
克鲁斯卡尔算法 (Kruskal’s Algorithm)
这是一种“贪婪 (greedy)”的方法。你只需寻找当前可选的最短边即可。
步骤：
1. 将图中所有的边按权重由小到大排列。
2. 选择权重最小的边。
3. 选择下一条最便宜的边。关键规则：如果加入这条边会形成回路，就跳过它！
4. 重复上述步骤，直到所有顶点都连通为止（对于 \(n\) 个顶点，你最后会有 \(n-1\) 条边）。
普里姆算法 (Prim’s Algorithm) - 图形版
普里姆算法与前者不同，它像植物生长根系一样，从起点开始扩展生成树。
步骤：
1. 从任何一个顶点开始。
2. 查看所有连接“已选顶点”到“未选顶点”的边。
3. 选择权重最短的那条边。
4. 重复步骤直到所有顶点都被包含在内。
普里姆算法 (Prim’s Algorithm) - 矩阵版
在考试中，你经常被要求使用距离矩阵 (distance matrix) 来执行普里姆算法。它看起来很吓人，但实际上非常有规律！
步骤：
1. 选择一个起始顶点（通常为 A），并在其栏位上方标记“1”。划掉 A 行。
2. 查看所有已标记栏位中的数值。
3. 在这些栏位中圈出最小值（忽略你已经划掉的行）。
4. 该圈选值所在的行即为下一个顶点。为其栏位标记下一个数字（例如“2”），并划掉该行。
5. 重复直到所有栏位都被标记为止。
常见错误：忘记划掉刚加入的顶点所在的行。如果不划掉它，你可能会不小心选到一条回到“已选顶点”的边！
重点总结：克鲁斯卡尔算法先对所有边进行排序；普里姆算法则是一次增加一个连通顶点来构建树。
2. 寻找最短路径
这是课程中关于“Google 地图”的部分。我们的目标是找出特定起点与终点之间的最短距离。
戴克斯特拉算法 (Dijkstra’s Algorithm)
此算法可找出从一个起点到网络中所有其他顶点的最短路径。
步骤：
1. 给起点一个永久标签 (permanent label) 0。
2. 对于每个连接到当前节点的节点，计算一个工作值 (working value)（到当前节点的距离 + 边的权重）。
3. 如果这个新值比之前的任何工作值小，就替换掉它。
4. 查看整个图中所有的工作值，选择最小的一个——这就成为该点的永久标签。
5. 从这个新的永久节点重复上述步骤，直到终点有了永久标签为止。
记忆小撇步：将戴克斯特拉算法想象成水从起点向外泛滥。永久标签告诉你“水”第一次到达该点的确切时间。
弗洛伊德算法 (Floyd’s Algorithm)
戴克斯特拉算法从一点出发，而弗洛伊德算法则找出图中每一对顶点之间的最短路径。它使用两个矩阵：距离矩阵 (Distance Matrix) 和路径矩阵 (Route Matrix)。
过程：
对于一个拥有 \(n\) 个顶点的图，你需要进行 \(n\) 次迭代。
在第 1 次迭代中，你使用顶点 1 作为“枢纽 (pivot)”。检查经由顶点 1 从 \(A\) 到 \(B\) 是否比当前从 \(A\) 到 \(B\) 的直接距离更短。
如果 \(Dist(A, 1) + Dist(1, B) < Dist(A, B)\)，则用新的较短距离更新矩阵。
快速回顾：戴克斯特拉适合“一对多”；弗洛伊德适合“多对多”。
3. 路线检查算法 (Route Inspection Algorithm)
又称为中国邮递员问题 (Chinese Postman Problem)。目标是走过每一条边至少一次并回到起点，同时使总距离最小化。
“奇数节点”的概念：
如果一个图的所有顶点度数（连接边的数量）均为偶数，该图即为欧拉图 (Eulerian)。你可以完美地遍历它。
如果图中有奇数节点，你必须重复走过某些边。在 Edexcel 教学大纲中，你将处理拥有最多四个奇数节点的网络。
步骤：
1. 找出所有的奇数顶点。
2. 列出这些奇数顶点的所有可能配对方式。
3. 找出每对之间的最短路径（必要时使用戴克斯特拉算法）。
4. 选择总权重最小的配对方式。
5. 将这些重复边的权重加到图的总权重中。
你知道吗？如果只有两个奇数节点，只需找出它们之间的最短路径并重复即可，很简单！
4. 旅行推销员问题 (Traveling Salesman Problem, TSP)
TSP 与路线检查不同。这里的目标是访问每一个顶点一次并回到起点，同时使距离最小化。这类问题很难完美解决，因此我们寻找界限 (Bounds)。
上界 (Upper Bounds，即“足够好”的路线)
上界是我们知道可以达到的距离，即使它不一定是绝对最好的。
1. 最近邻居算法 (Nearest Neighbour Algorithm)：从一个顶点开始，前往最近的未访问顶点。重复直到所有点都被访问，最后回到起点。
2. 双倍最小生成树 (Double MST)：找出 MST，然后将其边加倍（对每一条边来回走一次）。这总是一个有效的路径，但通常比较长。
下界 (Lower Bounds，即“不可能比这更好”的数值)
下界是一个理论最小值，你可能实际上无法达到它。
删除顶点法 (Deleted Vertex Method)：
1. 删除一个顶点及其所有连接的边。
2. 找出剩余顶点的最小生成树 (MST)。
3. 加上与被删除顶点相连的两条最短边的权重。
4. 结果即为下界。若要找到最佳下界，请针对不同的删除顶点重复此步骤，并选取最大的数值。
重点总结：实际的最优解位于你的最大下界 (Highest Lower Bound) 和最小上界 (Lowest Upper Bound) 之间。
总结检查清单
- MST：克鲁斯卡尔（针对边）或普里姆（针对顶点/矩阵）。
- 最短路径：戴克斯特拉（单一起点）或弗洛伊德（所有起点）。
- 每一条边：路线检查（配对奇数节点）。
- 每一个顶点：TSP（上界 = 最近邻居；下界 = 删除顶点 + MST）。
如果刚开始觉得很难，不用担心！学习算法最好的方法就是拿一张纸，画一个小网络，然后亲自动手执行步骤。你一定可以的！