图论算法：进阶数学中的决策指南

你好！欢迎来到决策数学 1 (D1) 的精彩世界。本章“图论算法”可能是进阶数学中最具实用性且直观的部分。它的一切核心都在于寻找最高效的解决方案——无论是寻找成本最低的连接、最快的路线，还是最短的配送行程。

如果“算法”这个词听起来很复杂，请不要担心。算法仅仅是一组用于解决特定问题的步骤，你可以把它看作一份数学菜谱！在读完这些笔记后，你将能够像专业的物流经理和网络工程师一样解决现实生活中的效率问题。

第 1 节：网络（图）基础

在我们运行算法之前，需要先理解图论的“语言”。

什么是图？

图（或网络）由点和连接它们的线组成。

  • 节点 (或 顶点)：图中的点（例如：城市、路口、计算机服务器）。
  • 弧 (或 边)：连接节点的线（例如：道路、电缆、航线）。
  • 权值：分配给弧的数值，通常代表距离、成本、时间或容量。

关键术语

  • 路径：沿着弧从一个节点走到另一个节点的路线。
  • 圈 (或 回路)：起点和终点相同的路径。
  • 度 (阶)：连接到某节点的弧的数量。
  • 连通图：图中任意两个节点之间都存在路径的图。
  • 简单图：没有环（起点和终点相同的弧）且任意两个节点间没有多条弧的图。
  • 有向图：弧带有箭头的图，意味着只能沿一个方向通行（例如：单行道）。

快速回顾： 图就是连接关系的直观图示，而权值则告诉我们这些连接有多“昂贵”。

第 2 节：最小生成树 (MST)

想象一下，你要用最便宜的光缆连接五座办公楼。你需要连接所有楼宇，但不希望电缆中存在任何不必要的循环（圈）。这就是最小生成树发挥作用的地方。

生成树是一个连通所有节点且不形成任何圈的子图。最小生成树 (MST) 是权值之和最小的生成树。

算法 2.1：克鲁斯卡尔算法 (Kruskal’s Algorithm，即“最便宜优先”法)

克鲁斯卡尔算法是一种贪心算法，它在每一步都专注于选择当前可用的最便宜的弧。

目标： 按权值递增的顺序添加弧来构建生成树，确保不形成任何圈。

克鲁斯卡尔算法步骤
  1. 将网络中所有的弧按权值从小到大排列。
  2. 从权值最小的弧开始。选择它并将其加入你的树中。
  3. 观察下一条权值最小的弧。将其加入，除非它与你已选择的弧形成了圈。
  4. 重复步骤 3，直到所有节点都被连通。

常见错误警示！ 克鲁斯卡尔算法的铁律是：千万不要形成圈！ 如果加入某条弧会将两个已经通过现有树路径连通的节点再次连接，则必须舍弃该弧。

克鲁斯卡尔算法要点： 从哪里开始均可，按权值大小顺序操作，并避开回路。

算法 2.2：普里姆算法 (Prim’s Algorithm，即“树的生长”法)

普里姆算法同样是贪心算法，但它专注于从起点开始向外不断“生长”树结构。

目标： 从一个节点开始，持续连接距离最近的未连通节点。

普里姆算法（网络法 - 直观化）
  1. 从任意节点开始（选哪个都行，但通常选 A）。标记它为“已在树中”。
  2. 观察所有连接“树内”节点和“树外”节点的弧。
  3. 在这些选项中选择权值最小的弧。
  4. 将选中的弧及其指向的新节点加入树中。
  5. 重复步骤 2-4，直到所有节点都被包含在树中。
普里姆算法（矩阵法）

当图以距离矩阵形式给出时，此方法非常有效。

  1. 先选择任意行/列（例如 A）。标记该列为“已包含”。
  2. 在已包含的行/列中，寻找最小的非零项。这就是第一条弧。
  3. 圈出该项并划掉相应的行（它现在已属于树的一部分）。
  4. 新加入的节点决定了你下一步要包含的列。
  5. 重复步骤 2-4，直到选中了 \(n-1\) 条弧（其中 \(n\) 为节点数）。

类比： 如果克鲁斯卡尔算法像是一群建筑工在全国范围内寻找最便宜的单条道路，普里姆算法则像是一个施工队从基地开始不断向外扩建。

第 3 节：最短路径 – 迪杰斯特拉算法 (Dijkstra’s Algorithm)

最小生成树以低成本连接所有节点。迪杰斯特拉算法解决的是另一个问题：在两个特定点（起点和终点）之间找到最快、最短或成本最低的路线。

迪杰斯特拉算法通过系统地为节点分配并更新标签（距离）来工作，直到确定了最短路径。

迪杰斯特拉算法核心概念

  • 标签：我们为每个节点分配标签 \((d, p)\)，其中 \(d\) 是从起点出发的距离，\(p\) 是到达该节点的前驱节点。
  • 临时标签：如果发现了更短的路径，标签可能会更改。
  • 永久标签：已经确定并确认为该节点最短距离的标签。一旦标签变为永久，就永远不会再改变。
迪杰斯特拉算法步骤
  1. 起始节点： 为起始节点分配一个永久标签 \((0, -)\)。所有其他节点获得临时标签，通常设为 \(( \infty, -)\) 或者初始留空。
  2. 扫描（展开）节点： 选择当前具有最小距离值 (\(d\)) 的永久标签节点。这就是你当前“所处”的节点。
  3. 更新邻居： 检查与当前节点连接的所有具有临时标签的节点。计算潜在的新总距离（旧的永久距离 + 弧的权值）。
  4. 重新标记： 如果新的总距离小于该节点的当前临时距离，则更新标签，记录新距离并将当前节点作为前驱节点。
  5. 固定为永久： 扫描完当前的永久节点后，观察所有剩余的临时标签。选择其中距离最小的一个，将其固定为永久（圈出该标签）。
  6. 重复： 返回步骤 2，扫描新固定的永久节点，直到目标节点被固定为永久标签。

记忆助手： 总是寻找最小的临时标签将其定为下一个永久标签。这一点至关重要！

常见错误警示！ 学生经常忘记在流程后期发现更短路径时更新临时标签。一定要时刻对比潜在的新路径与现有的临时标签！

迪杰斯特拉算法要点： 从起点开始向外扩散，逐一系统地确认到每个节点的最短路径。

第 4 节：路径检测（中国邮递员问题 - CPP）

想象一位邮递员或撒盐车司机必须经过每一条街道恰好一次，并返回站点，同时使总行驶距离最小化。

中国邮递员问题 (CPP) 要求找到经过网络中每一条弧的最短闭合路径。

奇偶节点规则

如果图中的每个节点都有偶数度（连接的弧的数量为偶数），邮递员就可以不重复任何弧完成路线。路线的总长即为所有弧权值之和。

如果存在奇数度节点，邮递员必须重复某些弧，使整个网络变得可遍历（欧拉回路）。

CPP 解决方案步骤
  1. 识别奇数节点： 列出所有度为奇数的节点。由于弧总是成对出现的，奇数节点的数量必须总是偶数（2 个、4 个、6 个等）。
  2. 配对奇数节点： 我们必须将奇数节点两两配对，并找到每对之间的最短路径。通过将这些最短路径中的弧重复一遍，我们实际上使奇数节点变成了“偶数”。
  3. 计算最短配对：
    • 如果有 2 个奇数节点 (A 和 B)，找到 A 和 B 之间的最短路径。
    • 如果有 4 个奇数节点 (A, B, C, D)，必须测试所有三种可能的配对情况：
      (i) (A 与 B 配对) 且 (C 与 D 配对)
      (ii) (A 与 C 配对) 且 (B 与 D 配对)
      (iii) (A 与 D 配对) 且 (B 与 C 配对)
    • 使用迪杰斯特拉算法或观察法找出每种配对方案的最短路径长度。
  4. 选择最小配对： 选择使增加的总路径长度最小的配对组合。
  5. 计算总路线长度：
    总长度 = (原网络中所有弧权值之和) + (最小增加路径长度)。
  6. 陈述需要重复的弧： 列出必须走两次的弧。

你知道吗？ 该算法以中国数学家管梅谷教授命名，他在 1962 年试图为邮递员寻找最优路线时提出了这个问题。

CPP 要点： 难点在于通过增加尽可能小的额外距离，将奇数节点转化为偶数节点。

第 5 节：旅行商问题 (TSP)

旅行商问题 (TSP) 的问题是：经过每一个节点（城市）恰好一次并回到起点的最短可能路线是什么？

所需的路线是最小权值的哈密顿圈。

与我们研究的其他算法不同，目前没有简单且有保证的算法能快速找到绝对的最优解（最优巡回）。对于大量的节点，寻找最优解在计算上成本太高。

相反，我们使用近似方法来寻找上界（已知可行的巡回）和下界（已知最优巡回不可能低于的距离）。

近似法 5.1：寻找上界

上界是任何有效哈密顿圈的长度（经过所有节点并回到起点）。寻找良好上界的最简单方法是使用最近邻算法。

最近邻算法
  1. 从指定的节点开始（如果没有指定，则尝试所有节点）。
  2. 从当前节点出发，选择通往最近的（未访问）节点的弧。
  3. 重复步骤 2，直到所有节点都被访问。
  4. 直接回到起始节点以完成巡回。
  5. 这个圈的总权值就是你的上界。

路线调整： 有时，微小的调整（交换两条弧）可以得到更短的巡回，从而提供更紧凑（更低）的上界。

近似法 5.2：寻找下界

下界是我们知道最优巡回必须达到或超过的最低成本。我们使用最小生成树 (MST) 或删除节点分析的概念来找到它。

使用最小生成树 (MST) 寻找下界

如果你从网络中删除任意节点及其相连的弧，剩余的图仍然需要通过生成树来连通。这是寻找下界的常用方法。

  1. 选择任意节点（例如 A）进行“删除”，并移除所有连接到它的弧。
  2. 使用普里姆或克鲁斯卡尔算法找到剩余节点的最小生成树 (MST)。计算其总权值。
  3. 识别最初连接到被删除节点 (A) 的两条最短弧。
  4. 计算下界：
    $$ \text{下界} = (\text{剩余节点的 MST 权值}) + (\text{连接到 A 的两条最短弧的权值}) $$

逻辑： 最优巡回必须离开 A 并回到 A。它必须至少使用两条与 A 相连的弧，并且必须连通剩余的节点——而连通剩余节点最便宜的方法就是通过 MST。

TSP 要点： 由于寻找精确答案太难，我们建立一个区间（上界到下界），最优解必然落在其中。

总结清单与学习建议

掌握算法要点
  • MST (克鲁斯卡尔/普里姆)： 重点在于以低成本连通所有节点，同时避开圈。矩阵计算优先用普里姆，快速视觉筛选用克鲁斯卡尔。
  • 最短路径 (迪杰斯特拉)： 处理临时标签时要细心。总是将最小的临时标签定为下一个永久标签。
  • CPP： 识别奇数节点，并计算配对它们所需的最小总权值。
  • TSP： 理解上界（有效的巡回）与下界（理论最小值）之间的区别。

鼓励的话： 决策数学是非常程序化的。在小网络上按部就班地练习每一种算法，直到操作变得驾轻就熟。你能行的！