0%
面向二部图的增广路算法
算法思路
- 搜索一条增广路
- 如果找到了：替换得到更大的匹配，返回1
- 否则结束
算法细节
- 每轮从二部图的任意一侧的不饱和顶点开始，搜索增广路，以左侧为例。
- 左侧到右侧，找不在匹配中的边；右侧到左侧，找在匹配中的边。
- 如果找到一个不是起点的未饱和顶点 则找到增广路 替换得到更大的匹配 转到5。
- 或深度优先搜索完所有的点和边，仍未找到增广路 本轮没找到增广路 转到5。
- 如果左侧还有不饱和的顶点没有搜索过，则转到1进入下一轮搜索。
算法正确性
- 算法一定会终止
- DFS不重复的搜索
每轮搜索一定会结束
- 总点数是有限的
替换更大的匹配只能进行有限次 轮数是有限的
- 算法一旦终止，找到的一定是最大匹配
- 存在增广路
一定能找到
- 不存在增广路
无增广路
找到最大匹配
算法时间复杂度
- 搜索的最大轮数:
- 每轮搜索的最大步骤数:
- 整个算法时间代价:
面向二部图的Hopcroft-karp算法
算法思路
- 在增广路算法基础上改进
- 总搜索最短的增广路
- 每轮搜索多条无公共顶点的增广路，全部替换
算法细节
- 每轮从二部图的任意一侧的所有不饱和顶点开始，搜索增广路，以左侧为例。
- 左侧到右侧，找不在匹配中的边；右侧到左侧，找在匹配中的边。
- 并发的利用广度优先搜索，对所有顶点进行分层；所有可能的起点构成第0层；与第i层相邻的所有未分层的顶点构成第i+1层。
- 若第k层包含未饱和的右侧顶点
在分层信息引导下反向DFS搜回第0层，找到增广路，并把找到了增广路做删除标记
第k层多个未饱和的右侧顶点可能找到多条无公共顶点的最短增广路。
- 若找不到增广路
无增广路
找到最大匹配；否则替换得到更大的匹配并返回步骤1。
算法正确性
- 算法一定会终止
- BFS不重复的搜索
每轮搜索一定会结束
- 总点数是有限的
替换更大的匹配只能进行有限次 轮数是有限的
- 算法一旦终止，找到的一定是最大匹配
- 存在增广路
一定能找到
- 不存在增广路
无增广路
找到最大匹配
算法时间复杂度
- 搜索的最大轮数:
- 每轮搜索的最大步骤数:
- 整个算法时间代价:
面向一般图的Edmonds算法
算法思路
- 在增广路算法的基础上改进
- 在每轮搜索中，如果一个顶点在本轮搜索中，已经经过长为偶数的交错路到达，同时又经过长为奇数的交错路到达，那么就发现了一个奇圈，两条路并称为flower；奇圈称为blossom
- 两条交错路的最长公共子路称为stem，其终点称为base
- stem的最后一条边在当前匹配中，否则再往后的一条边一定在匹配中，是唯一的，和奇圈矛盾
- blossom的顶点关联的边中，除blossom中的边和stem的最后一条边以外，其它都不在当前匹配中。(否则该边奇圈中的顶点在奇圈中的两条边都是未匹配的边，从而无法发现奇圈)
- 将blossom收缩为一个顶点：顶点合并，内部边删除、外部边保留
- 如果新图中有增广路，那么原图中一定有增广路
关键步骤
- 在搜索过程中，一旦发现奇圈，将其收缩成一个顶点，再继续搜索
- 如果新图中的增广路经过收缩后的顶点，那么利用奇圈中的两条交错路之一（恰有一条会符合要求）将其还原到原图的增广路
算法时间复杂度
- 朴素的实现：
- 合适的数据结构表示blossom和处理收缩：
- 一般图最大匹配的其他算法中，时间开销最少的能到达：
微信支付