简介：绘制决策制定的路线图
欢迎来到激动人心的图论算法世界！本章是决策数学（Decision Mathematics）的核心。虽然图看起来只是简单的示意图，但我们在这里学习的算法却是导航系统（如GPS）、物流、网络规划和社交媒体连接等领域所使用的基础工具。
简单来说，算法就是一套为解决特定问题而设计的指令。在本章中，我们将学习两类主要问题：寻找两点之间的最短路径，以及寻找连接所有点的最经济方式。
如果起初觉得有些棘手，不必担心；我们将逐步分解每一个过程。掌握这些技术需要有条理的思考，并仔细记录你的解题步骤。
快速回顾：图论术语（前置知识）
- 节点（或顶点）： 图中的一个点（例如，一个城市、一个交叉路口）。
- 边（或弧）： 连接两个节点的线（例如，一条道路、一条管道）。
- 权值： 与边相关联的数值（例如，距离、时间、成本）。
- 网络： 边具有权值的图。
- 路径： 沿着边所走的路线。
- 树： 一个没有环（回路）的连通图。
第1节：寻找最短路径 - 迪杰斯特拉算法 (Dijkstra's Algorithm)
迪杰斯特拉算法的目标
迪杰斯特拉算法用于寻找从单个起始节点到网络中每一个其他节点的最短（或最快、最便宜）路径。
类比：把它想象成规划从中心仓库（起始节点）到城市中每一位客户的最快送货路线。
迪杰斯特拉算法操作指南
该算法为每个节点使用两种类型的标签：
- 永久标签： 到该节点目前已知的确定的最短距离。一旦变为永久（或“打上框”），它就不能再改变。
- 临时标签： 通过潜在路线计算出的距离。如果发现了更短的路线，这些标签可以被更新（划掉旧的并替换为新的）。
步骤：
- 开始： 给起始节点打上一个永久标签 \(0\)。给这个数字加上方框。
- 扫描： 查看所有与最近打框的节点直接相连的未打框节点。
- 计算临时标签： 对于每个相连的未打框节点，计算它通过当前已打框节点到达起点的距离。
- 新标签 = (当前节点的永久标签) + (连接边的权值)
- 选择并打框： 从整个网络中所有未打框的节点中，选择最小的临时标签。将此标签变为永久（打上框）。
- 重复： 重复步骤2到4，直到目标节点（或所有节点）都有了永久（打框）标签。
如何追踪最短路径
完成算法后，要找到从起始节点到特定目标节点的实际路径，你必须从目标节点向后推导。
- 从目标节点开始。
- 查看其带框标签 \(L\)。找到一个前驱节点 \(P\)，使得 \((\text{节点 } P \text{ 的标签}) + (\text{边 } P \to D \text{ 的权值}) = L\)。
- 最短路径仅包含那些权值对永久标签总和有贡献的边。
⚠ 避免常见错误
一个非常常见的错误是仅根据起始节点来计算临时标签。请记住，你必须始终根据最近打框的节点来更新临时标签。此外，一旦标签变为永久（打框），你可以利用它来扫描，但绝不能改变它的值。
迪杰斯特拉算法的核心要点： 迪杰斯特拉方法是通过始终使当前可用的最短路线永久化，从而逐步向外找到最短路径。
第2节：连接所有节点 - 最小生成树 (MST)
什么是生成树？
想象一下，你有多个位置（节点）需要用电缆或道路（边）进行连接。生成树是一种边的选择，它连接了网络中的所有节点，使用了所需的最小边数，且至关重要的是，不形成任何环（回路）。
什么是最小生成树 (MST)？
最小生成树 (MST) 是一种生成树，其所选边的总权值尽可能小。
类比：如果你要在几个城镇之间建立电话网络，你希望确保每个城镇都连接在一起，但同时要使铺设电缆的总长度（从而成本）最小化。
我们使用两种强大的算法来寻找MST：普里姆算法（Prim's Algorithm）和克鲁斯卡尔算法（Kruskal's Algorithm）。它们总是得出相同的最小总权值，但解决问题的方法不同。
第3节：普里姆算法 (Prim's Algorithm)（节点聚焦法）
普里姆算法通过从起始节点向外扩展来构建MST。这是一种基于节点的方法。
记忆窍门：P代表Prim's，P代表Proximity（邻近）——我们总是选择距离当前正在增长的树最近的边。
方法1：在网络图上使用普里姆算法
步骤：
- 开始： 选择任意节点作为树的起点。标记该节点为“在树中”（通常通过高亮显示它或其相连的边）。
- 扫描： 查看所有与当前在树中的节点相连的边。
- 选择： 从这些扫描的边中选择权值最小的一条，并确保这条边连接的是一个尚未在树中的节点。
- 添加： 将这条最小权值的边及其连接的新节点加入树中。
- 重复： 重复步骤2到4，直到所有节点都包含在树中。
- 总权值： 将所选边的权值相加，得出总的最小权值。
⚠ 普里姆算法的关键规则
你只能考虑与已选节点相连的边。一旦某条边与树中现有的边形成了环，即使它的权值最小，你也必须忽略它。
方法2：使用矩阵（表）进行普里姆算法
当网络复杂时，使用代价矩阵可以高效地执行普里姆算法。
- 开始： 选择起始行/节点（例如，节点A）。标记该行已“访问”（例如，划掉该行）。
- 扫描行： 查看所选行并找到最小的非零条目。高亮该条目并记录这条边。
- 选择列： 你高亮的条目对应一个新节点（列标题）。划掉这个新节点的行和列。
- 重新扫描： 现在，只查看尚未划掉的节点的列。找到所有活跃行（已在树中的节点的行）中的最小权值。
- 重复： 继续选择未划掉的最小值，直到选择了 \(n-1\) 条边（其中 \(n\) 是节点总数）。
普里姆算法的核心要点： 普里姆算法是一种贪婪的局部优化方法。它总是选择从当前已连接到树的节点出发最便宜的边。
第4节：克鲁斯卡尔算法 (Kruskal's Algorithm)（边聚焦法）
克鲁斯卡尔算法通过观察整个网络并纯粹根据权值选择边来构建MST，而不考虑它们的位置，只要它们不形成环。
记忆窍门：K代表Kruskal's，K代表Kicking out Cycles（踢出环路）。该算法的核心在于按顺序选择边，并拒绝任何会构成闭合回路的边。
克鲁斯卡尔算法的步骤
- 列出并排序： 列出网络中所有的边，并按权值升序（从小到大）排序。
- 选择边： 顺着排序列表向下选择边。
- 检查环路： 在选择一条边之前，检查添加它是否会与已选择的边形成环（闭合回路）。
- 如果该边不会形成环，则选择它（将其添加到MST中）。
- 如果该边会形成环，则拒绝它，并移动到列表中的下一条边。
- 停止条件： 当你选择了 \(n-1\) 条边时停止，其中 \(n\) 是网络中的节点总数。所有节点必须保持连通。
- 总权值： 将所选边的权值相加。
克鲁斯卡尔算法选择示例
想象你的列表从以下开始：边AB（权值2），边CD（权值3），边AC（权值4），边BC（权值5）...
1. 选择AB（2）。树开始建立。
2. 选择CD（3）。没问题，它与AB不相连。
3. 选择AC（4）。没问题，它连接了A和C。
4. 考虑BC（5）。如果我们选择BC，会形成一个环：A-B-C-A。因此，拒绝边BC。
比较：普里姆 vs. 克鲁斯卡尔
两种算法都能达到相同的结果（MST），但在实际应用中：
- 如果网络是以矩阵（距离表）形式表示，普里姆算法通常更容易使用。
- 如果网络是以长边列表形式表示，克鲁斯卡尔算法通常更容易使用。
克鲁斯卡尔算法的核心要点： 克鲁斯卡尔算法是一种全局优化方法。先将所有边排序，然后按成本增加边，并不断检查以确保永不形成闭合回路。
总结与鼓励
祝贺你！你已经掌握了决策数学1中的三个基础算法：
- 迪杰斯特拉算法： 寻找从一个节点到所有其他节点的最短路径（节点永久标签法）。
- 普里姆算法： 通过添加最近的未访问节点来构建最小生成树（节点聚焦法）。
- 克鲁斯卡尔算法： 通过按成本顺序选择边并避免环路来构建最小生成树（边聚焦法）。
这一章成功的关键在于练习。每种算法都是一个结构化的过程。坚持步骤，在标记和检查时细致入微，你一定能掌握这些至关重要的技巧！
你知道吗？
艾兹格·迪杰斯特拉 (Edsger Dijkstra) 在1956年与妻子喝咖啡时发明了他的最短路径算法，并在约20分钟内解决了这个问题！这表明即使是最著名的算法，也可以从简单的逻辑步骤中推导出来。