欢迎来到图论算法！

在本章中，我们将探索决策数学（Decision Mathematics）中最实用的工具。如果你曾经好奇 Google 地图是如何找出最快的回家路线，或是公司如何设计线缆网络以节省最多的材料，现在你即将揭开这些谜底！

决策数学的核心就是效率——在节省时间、金钱或资源的同时，找出处理问题的最佳方案。别担心，这些算法初看之下步骤繁琐，但它们其实只是一套我们必须遵守的逻辑“食谱”。让我们开始吧！

1. 基础概念：什么是图 (Graph)？

在进入算法之前，我们必须先掌握基础术语。在决策数学中，图 (Graph) 并非 x-y 轴上的曲线，而是一系列点与线的集合。

关键术语：
• 顶点 (Vertices 或 Nodes)： 图上的点。
• 边 (Edges 或 Arcs)： 连接顶点的线。
• 权重 (Weight)： 标注在边上的数值（代表距离、成本或时间）。
• 网络 (Network)： 每条边都有权重的图。
• 路径 (Path)： 一连串的边，且过程中不会经过同一个顶点两次。
• 环 (Cycle)： 起点与终点为同一个顶点的路径（即封闭回路）。
• 树 (Tree)： 一个连通且没有环的图。
• 生成树 (Spanning Tree)： 一棵连接图中所有顶点的树。

快速回顾： 试着将“树”想象成家族树（家谱）——无论你向下追溯多远，都不会绕圈回到原点！

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

想像你是电讯工程师，需要连接 5 个城市并铺设光纤。你希望所有城市都能连接到网络，但总铺设成本（线缆长度）必须最低。这就是最小生成树问题。

我们主要使用两种算法来解决：克鲁斯卡尔算法 (Kruskal’s Algorithm) 与 普里姆算法 (Prim’s Algorithm)。

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

这是一种“贪婪”算法。它单纯地从整个网络中寻找最短的边，而不考虑它们的位置。

逐步教学：
1. 将网络中所有的边按权重由小到大排列。
2. 选取最短的边，将其加入你的 MST。
3. 选取下一条最短的边。仅在不会产生环（封闭回路）的情况下将其加入。
4. 重复上述步骤，直到所有顶点都连通。若有 \(n\) 个顶点，你将刚好需要 \(n-1\) 条边。

常见错误： 同学们常忘记检查是否会产生“环”！务必问自己：“如果我加入这条边，会不会形成一个圈？”如果答案是肯定的，就跳过这条边！

普里姆算法 (Prim’s Algorithm，适用于网络图)

普里姆算法像是一种“生长”算法。它从一个顶点开始，像藤蔓一样向最近的邻居延伸。

逐步教学：
1. 随意挑选一个起点顶点。
2. 检查所有连接“已选顶点”与“未选顶点”的边。
3. 挑选权重最小的边并将其加入。
4. 重复步骤直到所有顶点都进入树中。

你知道吗？ 与 Kruskal’s 不同，Prim’s 算法天生就能避免产生环，因为你始终是将一个“新”顶点连接到“已选”的群组中。

普里姆算法 (使用矩阵)

有时网络会以表格（距离矩阵）形式提供，而非图形。课程大纲明确要求你必须掌握这种操作方法。

逐步教学：
1. 选择一个起点顶点（通常是第一列），并删除该列。将该顶点的栏位标记为“1”。
2. 检视所有已标记（例如“1”）栏位中的数字。
3. 找出这些栏位中的最小值。该值所在的列即为下一个要加入的顶点。
4. 写下该边及其权重。删除该新顶点所在的列，并将其栏位标记为下一个数字（例如“2”）。
5. 重复步骤直到所有列都被删除。

关键总结： Kruskal’s 是在图上各处零散地建立树的片段，而 Prim’s 则是从一点出发，建立一个不断长大的单一树状结构。

3. 戴克斯特拉算法 (Dijkstra’s Algorithm，最短路径)

Dijkstra’s 算法用于寻找从单一起点到终点的最短路径。这正是卫星导航的运作原理！

我们在顶点上使用特殊的标记系统。每个顶点都有一个三部分的标签格：
1. 标记顺序： 该顶点何时被设为“永久”？
2. 最终（永久）标签： 从起点到该处的最短实际距离。
3. 工作数值： 当我们发现更好的路径时，会更新这些暂时的距离。

逐步教学：
1. 将起点顶点的永久标签设为 0，标记顺序为 1。
2. 更新： 针对刚设为永久的顶点，检查其所有连接的邻居。计算到它们的距离（当前节点距离 + 边权重）。
3. 将结果写为该邻居的工作数值。如果该处已有数值，只有在取得更小数值时才进行替换。
4. 选择： 检视整个图中所有工作数值。挑选出最小的一个，使其成为下一个永久标签。
5. 重复直到你的终点顶点被设为永久为止。

别担心，初学时可能会觉得很复杂！ 只要记住黄金法则：在检查过所有其他可能到达的路径前，绝对不要将工作数值设为永久。整个图中最小的工作数值永远是你的下一个选择目标。

找出路径： 完成后，如何确认该走哪条路？从终点往回推！若满足以下条件，则该顶点位于最短路径上：
\( (顶点 \ B \ 的数值) - (顶点 \ A \ 的数值) = 边 \ AB \ 的权重 \)

快速回顾：
• Kruskal/Prim： 用于连接所有人并取得最低总成本。
• Dijkstra： 用于连接某两点以取得单程最短路径。

4. 关键技能总结

要掌握这一章，你需要具备以下能力：
• 说明路径 (path) 与 环 (cycle) 的区别。
• 透过边的排序并避开环来执行 Kruskal’s 算法。
• 在图形上执行 Prim’s 算法，总是选择离现有树最近的“邻居”。
• 在矩阵上执行 Prim’s 算法，透过标记栏位与删除列来完成。
• 使用“标签格”方法执行 Dijkstra’s 算法，以找出两点间的最短路径。

最后提示： 在考试中执行这些算法时，请务必写下每个步骤！即使最终答案正确，评分标准通常也会包含边的排序列表（Kruskal’s）或是标签格中的工作数值更新过程（Dijkstra’s）。