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

简介:

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

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

目录
相关文章
|
5月前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
5月前
|
算法
力扣经典150题第二十一题:反转字符串中的单词
力扣经典150题第二十一题:反转字符串中的单词
60 0
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
6月前
|
算法
白话 KMP 算法
白话 KMP 算法
38 2
|
6月前
|
存储 算法
图解Kmp算法——配图详解(超级详细)
图解Kmp算法——配图详解(超级详细)
|
存储 算法
算法:图解前缀和问题
算法:图解前缀和问题
|
算法 C++
剑指offer(C++)-JZ38:字符串的排列(算法-搜索算法)
剑指offer(C++)-JZ38:字符串的排列(算法-搜索算法)
|
存储 算法
算法分类数组经典题目
算法分类数组经典题目
|
人工智能 算法 JavaScript
[数据结构与算法]基础算法(排序, 二分, 前缀, 差分)
快速排序:(分治的思想)✅ 确定分界点:q[l], q[(r+l)/2], q[r] (中间点可以随机选, 按照同一规则, 这里选(l+r)/2该点) 维护数组:维护分界点的左边都比分界点小,分界点的右边都比分界点大 按照维护关系, 递归处理左右两段 💡思想解释: 先整后细:先让大体总的符合条件,再部分部分解决
|
机器学习/深度学习 算法 Python
Python实现回溯算法求解括号生成
Python实现回溯算法求解括号生成
61 0