二分匹配最大匹配的理解(附图解)

简介:

  定义
一个PXP的有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联;(如果把这些路径中的每条路径从它的起始点走到它的终点,那么恰好可以经过图中的每个顶点一次且仅一次);如果不考虑图中存在回路,那么每条路径就是一个弱连通子集.
由上面可以得出:
1.一个单独的顶点是一条路径;
2.如果存在一路径p1,p2,......pk,其中p1 为起点,pk为终点,那么在覆盖图中,顶点p1,p2,......pk不再与其它的顶点之间存在有向边.
路径覆盖与二分图匹配的关系(必须是有向无环图):
最小路径覆盖=|P|-最大匹配数

也就是说匈牙利算法将一个二分匹配模型转换成了一个有向图的关系(u->v)存在了二维数组中!最后通过linker[u]数组的值,我们知道是选择了linker[u] -> u这一条有向边的匹配关系!也就是有多少个非负的linker[u]的个数,就有多少个匹配的关系!如果不存在回路,那么这些linker[u] -> u有向边关系所构成的弱联通的子集的个数就是最小路径覆盖的个数!

目录
相关文章
|
6月前
|
算法
【动态规划专栏】背包问题:分割等和子集
【动态规划专栏】背包问题:分割等和子集
62 0
|
3月前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
6月前
|
算法
算法题解-实现前缀树
算法题解-实现前缀树
|
存储 算法
算法:图解前缀和问题
算法:图解前缀和问题
|
人工智能 算法 JavaScript
[数据结构与算法]基础算法(排序, 二分, 前缀, 差分)
快速排序:(分治的思想)✅ 确定分界点:q[l], q[(r+l)/2], q[r] (中间点可以随机选, 按照同一规则, 这里选(l+r)/2该点) 维护数组:维护分界点的左边都比分界点小,分界点的右边都比分界点大 按照维护关系, 递归处理左右两段 💡思想解释: 先整后细:先让大体总的符合条件,再部分部分解决
|
算法 前端开发 C++
拓扑排序详解(包含算法原理图解、算法实现过程详解、算法例题变式全面讲解等)
拓扑排序详解(包含算法原理图解、算法实现过程详解、算法例题变式全面讲解等)
830 0
|
算法
【算法竞赛进阶指南】棋盘覆盖(二分图最大匹配)
【算法竞赛进阶指南】棋盘覆盖(二分图最大匹配)
142 0