xxx 无向图的最大匹配问题（Blossom 算法）
字数 3017 2025-12-08 05:20:34

xxx 无向图的最大匹配问题（Blossom 算法）

好的，我将为你详细讲解一个尚未在列表中出现过的经典图论算法——无向图的最大匹配问题（Blossom算法），也称为Edmonds’ Blossom算法。它用于求解一般无向图（不一定是二分图）的最大基数匹配问题。

1. 问题描述

我们有一个无向图 G = (V, E)，其中 V 是顶点集，E 是边集。

  • 匹配（Matching）： 匹配 M 是 E 的一个子集，满足其中任意两条边都没有公共顶点。也就是说，M 中的每条边连接的两个顶点都是“配对”的，且每个顶点在 M 中最多出现一次。
  • 最大匹配（Maximum Matching）： 是图中包含边数最多的匹配。
  • 饱和点（Matched Vertex）： 如果一个顶点与匹配 M 中的某条边相关联，则称该顶点被 M 饱和。
  • 未饱和点（Free Vertex）： 不与任何匹配边相关联的顶点。

目标： 找到一个匹配 M，使得匹配的边数最大。

为什么需要专门的算法？ 对于二分图，我们有高效的匈牙利算法或Hopcroft-Karp算法。但一般无向图可能存在奇环（长度为奇数的环），这会给寻找增广路带来巨大困难。Blossom算法的核心创新就在于它能优雅地“收缩”这些奇环（称为“花”），将图简化后继续寻找增广路。

2. 核心概念与基础

在深入算法之前，必须理解几个关键概念：

  • 交错路（Alternating Path）： 一条路径，其边交替地属于匹配 M 和非匹配边 (E \ M)。

  • 增广路（Augmenting Path）： 一条起点和终点都是未饱和点的交错路。其一个重要性质是：非匹配边的数量比匹配边的数量多1。

    • 这是算法的核心！Berge定理指出：一个匹配是最大匹配，当且仅当图中不存在关于该匹配的增广路。
    • 如果我们找到一条增广路 P，我们可以通过将 P 上所有边的状态反转（匹配边变非匹配，非匹配边变匹配），从而得到一个新的匹配，其边数比原匹配 多1。这个过程叫做增广（Augmentation）。

  • 花（Blossom）： 在寻找交错路的过程中，我们可能会遇到一个奇环（长度为奇数的环），这个奇环由偶数条（2k条）匹配边和（2k+1）条边（匹配与非匹配边交错）构成，并且环上存在唯一的顶点（称为“花托”或“花梗”），使得从该顶点到起点和到环的其他部分都能形成交错结构。这个奇环就被称为一朵“花”。

  • 收缩（Shrinking）： 这是Blossom算法的精髓。当我们发现一朵花 B 时，我们可以将整个花收缩成一个超级顶点（称为伪顶点）。收缩后，与花中任何顶点相连的边，现在都连接到这个超级顶点上。这个过程将原图 G 转换为一个更小的图 G’。我们可以在 G’ 中继续寻找增广路。

3. Blossom 算法步骤详解

算法从一个空匹配开始，通过迭代地寻找增广路并增广来逐步扩大匹配。寻找增广路的过程类似于二分图的匈牙利算法，但更为复杂。

步骤 1: 初始化

  • 设当前匹配 M 为空。
  • 将所有顶点标记为“未饱和”。

步骤 2: 寻找增广路

这是一个广度优先搜索（BFS） 或类BFS的过程。

  1. 选择一个未饱和点 r 作为本次搜索的根（Root），开始构建一棵交错树。这棵树的根 r 位于第0层（偶数层）。
  2. 树的构建规则：
    • 偶数层顶点（包括根）： 我们沿着非匹配边从其扩展。如果到达的顶点 w 是未饱和的，且不在当前树中，我们将其加入树中，成为奇数层顶点，并记录路径。
    • 奇数层顶点： 我们只能沿着匹配边从其扩展。因为匹配边连接的必然是另一个被匹配的顶点 v，我们将 v 加入树中，成为偶数层顶点。
  3. 在扩展过程中，我们可能会遇到以下四种情况：
    • 情况A：到达一个未访问的未饱和点（且不是起点）： 我们成功找到了一条从根 r 到另一个未饱和点的交错路 -> 这是一条增广路！ 转到步骤3进行增广。
    • 情况B：到达一个已访问的偶数层顶点： 这意味着我们找到了一个环。由于我们是从偶数层通过非匹配边到达另一个偶数层，这个环的边数是奇数（偶数->奇数(非匹配) -> 偶数(匹配) -> ... -> 偶数）。我们找到了一朵“花”。转到步骤4处理花。
    • 情况C：到达一个已访问的奇数层顶点： 这是正常现象，无需特殊处理，忽略这条边继续搜索即可。
    • 情况D：无法再扩展： 以当前根 r 为起点的搜索结束，没有找到增广路。返回步骤2，选择另一个未饱和的根重新开始搜索。如果所有未饱和点都已尝试过，算法结束，当前 M 即为最大匹配。

步骤 3: 增广

如果我们在图 G（或收缩后的图 G’）中找到了一条增广路 P，我们沿着记录的回溯路径，将 P 上的所有边反转状态。匹配边数加一。

  • 重要细节：如果增广路是在一个包含伪顶点的收缩图上找到的，我们需要先将伪顶点展开，恢复成原来的花，然后在展开后的花中找到一条正确的增广路径穿过它，再对整个路径进行增广。

步骤 4: 处理花（收缩）

当我们遇到情况B（找到花）时：

  1. 识别出构成花的奇环 B。找到花中两个偶数层顶点到根 r 的路径的第一个公共祖先，这就是“花托”。
  2. 将整个环 B 连同其内部结构收缩成一个伪顶点 b。
  3. 更新图：所有与环 B 中任何顶点相连的边，现在都看作与 b 相连。匹配关系也需要调整，原来连接环内外的唯一一条匹配边（连接花托和环外顶点）现在被视为连接 b 与外界。
  4. 在收缩后的新图 G’ 中，继续从当前的搜索状态（BFS队列）进行搜索，就好像这个伪顶点 b 从一开始就在那里一样。这保证了搜索的连续性。

步骤 5: 回溯与展开

  • 如果在收缩后的图 G’ 中找到了增广路，并且这条路经过了伪顶点，那么在应用增广操作前，必须将涉及的伪顶点递归地展开。
  • 展开时，需要在花内部找到一条交错路径，该路径的一端是进入花的顶点，另一端是离开花的顶点，并且能够将花内部的顶点正确地配对，使得整个展开后的路径是一条合法的增广路。

步骤 6: 算法终止

当不存在任何未饱和点可以作为根找到增广路时，算法终止。根据Berge定理，此时的匹配 M 就是图 G 的最大匹配。

4. 算法复杂度与总结

  • 时间复杂度： 朴素的Blossom算法实现是 O(|V|^4)。但通过精心的数据结构和实现（例如使用并查集维护花的收缩与展开，以及高效的LCA查询），可以优化到 O(|V|^3)。对于稠密图，这是一个非常实用的算法。
  • 核心思想： “寻找增广路” 和 “花的收缩”。收缩操作将奇环简化，使得在一般无向图上也能像在二分图上一样，通过BFS系统地寻找增广路。展开操作则确保了最终能在原图上构造出正确的匹配。

总结流程： 初始化匹配 -> 选未饱和根BFS -> 遇花则收缩 -> 找到增广路则增广（可能需要展开）-> 更新匹配 -> 重复直到无法找到增广路。

Blossom算法是图论中一个非常巧妙和强大的算法，它将二分图匹配的增广路思想成功推广到了任意无向图，其“收缩-展开”的思想在解决其他图论问题时也常被借鉴。

xxx 无向图的最大匹配问题（Blossom 算法） 好的，我将为你详细讲解一个尚未在列表中出现过的经典图论算法—— 无向图的最大匹配问题（Blossom算法） ，也称为Edmonds’ Blossom算法。它用于求解一般无向图（不一定是二分图）的最大基数匹配问题。 1. 问题描述 我们有一个 无向图 G = (V, E) ，其中 V 是顶点集， E 是边集。 匹配（Matching） ： 匹配 M 是 E 的一个子集，满足其中任意两条边都没有公共顶点。也就是说， M 中的每条边连接的两个顶点都是“配对”的，且每个顶点在 M 中最多出现一次。 最大匹配（Maximum Matching） ： 是图中包含边数最多的匹配。 饱和点（Matched Vertex） ： 如果一个顶点与匹配 M 中的某条边相关联，则称该顶点被 M 饱和。 未饱和点（Free Vertex） ： 不与任何匹配边相关联的顶点。 目标 ： 找到一个匹配 M ，使得匹配的边数最大。 为什么需要专门的算法？ 对于 二分图 ，我们有高效的匈牙利算法或Hopcroft-Karp算法。但一般无向图可能存在奇环（长度为奇数的环），这会给寻找增广路带来巨大困难。Blossom算法的核心创新就在于它能优雅地“收缩”这些奇环（称为“花”），将图简化后继续寻找增广路。 2. 核心概念与基础 在深入算法之前，必须理解几个关键概念： 交错路（Alternating Path） ： 一条路径，其边交替地属于匹配 M 和非匹配边 (E \ M) 。 增广路（Augmenting Path） ： 一条 起点和终点都是未饱和点 的交错路。其一个重要性质是：非匹配边的数量比匹配边的数量 多1 。 这是算法的核心！ Berge定理 指出：一个匹配是最大匹配，当且仅当图中不存在关于该匹配的增广路。 如果我们找到一条增广路 P ，我们可以通过将 P 上所有边的状态反转（匹配边变非匹配，非匹配边变匹配），从而得到一个新的匹配，其边数比原匹配 多1 。这个过程叫做 增广（Augmentation） 。 花（Blossom） ： 在寻找交错路的过程中，我们可能会遇到一个 奇环（长度为奇数的环） ，这个奇环由偶数条（2k条）匹配边和（2k+1）条边（匹配与非匹配边交错）构成，并且环上存在唯一的顶点（称为“花托”或“花梗”），使得从该顶点到起点和到环的其他部分都能形成交错结构。这个奇环就被称为一朵“花”。 收缩（Shrinking） ： 这是Blossom算法的精髓。当我们发现一朵花 B 时，我们可以将整个花 收缩 成一个 超级顶点 （称为 伪顶点 ）。收缩后，与花中任何顶点相连的边，现在都连接到这个超级顶点上。这个过程将原图 G 转换为一个更小的图 G’ 。我们可以在 G’ 中继续寻找增广路。 3. Blossom 算法步骤详解 算法从一个空匹配开始，通过迭代地 寻找增广路 并 增广 来逐步扩大匹配。寻找增广路的过程类似于二分图的匈牙利算法，但更为复杂。 步骤 1: 初始化 设当前匹配 M 为空。 将所有顶点标记为“未饱和”。 步骤 2: 寻找增广路 这是一个 广度优先搜索（BFS） 或类BFS的过程。 选择一个未饱和点 r 作为本次搜索的 根（Root） ，开始构建一棵 交错树 。这棵树的根 r 位于第0层（偶数层）。 树的构建规则： 偶数层顶点（包括根） ： 我们沿着 非匹配边 从其扩展。如果到达的顶点 w 是未饱和的，且不在当前树中，我们将其加入树中，成为奇数层顶点，并记录路径。 奇数层顶点 ： 我们只能沿着 匹配边 从其扩展。因为匹配边连接的必然是另一个被匹配的顶点 v ，我们将 v 加入树中，成为偶数层顶点。 在扩展过程中，我们可能会遇到以下四种情况： 情况A：到达一个未访问的未饱和点（且不是起点） ： 我们成功找到了一条从根 r 到另一个未饱和点的交错路 -> 这是一条增广路！ 转到步骤3进行增广。 情况B：到达一个已访问的偶数层顶点 ： 这意味着我们找到了一个环。由于我们是从偶数层通过非匹配边到达另一个偶数层，这个环的边数是奇数（偶数->奇数(非匹配) -> 偶数(匹配) -> ... -> 偶数）。 我们找到了一朵“花” 。转到步骤4处理花。 情况C：到达一个已访问的奇数层顶点 ： 这是正常现象，无需特殊处理，忽略这条边继续搜索即可。 情况D：无法再扩展 ： 以当前根 r 为起点的搜索结束，没有找到增广路。返回步骤2，选择另一个未饱和的根重新开始搜索。如果所有未饱和点都已尝试过，算法结束，当前 M 即为最大匹配。 步骤 3: 增广 如果我们在图 G （或收缩后的图 G’ ）中找到了一条增广路 P ，我们沿着记录的回溯路径，将 P 上的所有边反转状态。匹配边数加一。 重要细节：如果增广路是在一个包含伪顶点的收缩图上找到的，我们需要先将伪顶点 展开 ，恢复成原来的花，然后在展开后的花中找到一条正确的增广路径穿过它，再对整个路径进行增广。 步骤 4: 处理花（收缩） 当我们遇到情况B（找到花）时： 识别出构成花的奇环 B 。找到花中两个偶数层顶点到根 r 的路径的第一个公共祖先，这就是“花托”。 将整个环 B 连同其内部结构收缩成一个伪顶点 b 。 更新图：所有与环 B 中任何顶点相连的边，现在都看作与 b 相连。匹配关系也需要调整，原来连接环内外的唯一一条匹配边（连接花托和环外顶点）现在被视为连接 b 与外界。 在收缩后的新图 G’ 中， 继续从当前的搜索状态（BFS队列）进行搜索 ，就好像这个伪顶点 b 从一开始就在那里一样。这保证了搜索的连续性。 步骤 5: 回溯与展开 如果在收缩后的图 G’ 中找到了增广路，并且这条路经过了伪顶点，那么在应用增广操作前，必须将涉及的伪顶点 递归地展开 。 展开时，需要在花内部找到一条交错路径，该路径的一端是进入花的顶点，另一端是离开花的顶点，并且能够将花内部的顶点正确地配对，使得整个展开后的路径是一条合法的增广路。 步骤 6: 算法终止 当不存在任何未饱和点可以作为根找到增广路时，算法终止。根据Berge定理，此时的匹配 M 就是图 G 的最大匹配。 4. 算法复杂度与总结 时间复杂度 ： 朴素的Blossom算法实现是 O(|V|^4) 。但通过精心的数据结构和实现（例如使用并查集维护花的收缩与展开，以及高效的LCA查询），可以优化到 O(|V|^3) 。对于稠密图，这是一个非常实用的算法。 核心思想 ： “寻找增广路” 和 “花的收缩” 。收缩操作将奇环简化，使得在一般无向图上也能像在二分图上一样，通过BFS系统地寻找增广路。展开操作则确保了最终能在原图上构造出正确的匹配。 总结流程 ： 初始化匹配 -> 选未饱和根BFS -> 遇花则收缩 -> 找到增广路则增广（可能需要展开）-> 更新匹配 -> 重复直到无法找到增广路。 Blossom算法是图论中一个非常巧妙和强大的算法，它将二分图匹配的增广路思想成功推广到了任意无向图，其“收缩-展开”的思想在解决其他图论问题时也常被借鉴。