重庆秀山网站建设价格,google chrome官网,html情人节给女朋友做网站,wordpress 静态插件无向图的匹配问题 之所以把无向图的这个匹配问题放到最后讲是因为匹配问题借鉴了有向图中一些算法的思想 1 最大匹配和完美匹配
二分图回顾 二分图#xff1a;把一个图中的所有顶点分成两部分#xff0c;如果每条边的两端分别属于不同部分#xff0c;则这个图是二分图。更多…无向图的匹配问题 之所以把无向图的这个匹配问题放到最后讲是因为匹配问题借鉴了有向图中一些算法的思想 1 最大匹配和完美匹配
二分图回顾 二分图把一个图中的所有顶点分成两部分如果每条边的两端分别属于不同部分则这个图是二分图。更多二分图内容参考第4章 二分图相关 最大匹配和完全匹配的概念
一旦在二分图中找到一条边是我们想要的匹配那么这两个点在下面的匹配就不能再被访问了(类似相亲时两个人看对眼了其他相亲的就不能掺和了)。在二分图中像上面那样的匹配最多有多少对就是最大匹配问题(类似一堆人去相亲最多能成多少对)如果所有顶点都找到了自己的匹配那么这个最大匹配就成了完全匹配(即一堆人去相亲每个人在不干涉其他成功牵手的情侣前提下都找到了自己心仪的对象) 完全匹配一定是最大匹配但是最大匹配不一定是完全匹配。
2 无向图的最大匹配问题转化为有向图的最大流问题 所有边的容量都为1最大流即为最大匹配数 3 实现二分图匹配算法
实现代码测试代码
4 LeetCode LCP4.覆盖
题目分析 可以用黑白两种颜色覆盖栅格两种颜色的格子可以看做二分图则问题可以转换为二分图的最大匹配问题 黑白块的坐标规律 代码实现
代码实现
5 匈牙利算法不借助有向图和网络流模型求解最大匹配问题
匈牙利算法的定义 下面的增广路径是指首尾都是非匹配点的路径和上一章残量图中的增广路径不同 1.在二分图中2.从左侧的一个非匹配点出发3.从右向左的边永远走匹配边4.匹配边和非匹配边交替出现(称为交替路)5.终止与另外一个非匹配点(即增广路径首尾都是非匹配点) 交替路和增广路径的区别增广路径是起始点都是非匹配点的交替路。增广路径一定是交替路但交替路不一定是增广路径 6.有增广路径意味着最大匹配数可以加17.遍历完左侧所有尚未匹配的点即找到最大匹配
总结匈牙利算法就是对二分图左侧每个尚未匹配的点不断地寻找可以增广的交替路的过程。 可以用前面的BFS来实现不同的是来到二分图的右侧的点不需要寻路代码中的那个队列只存储左边的顶点。 匈牙利算法距离模拟
以下图为例.匹配即配对相当于相亲中的一对人一旦看对眼别人就不能插足了每次匹配起始都是左侧-右侧。匈牙利算法的核心对每条增广路径上顶点的匹配状态取反(非匹配边变匹配边匹配边变非匹配边)则可以多得到一条匹配边直到找到所有的匹配边。 1.先把左侧的0开始把0-4匹配到一起(匹配顶点标为蓝色代表已访问匹配顶点之间的边标为红色)2.第1次找增广路径 再从左侧的1开始访问到右侧的邻接点44已经被访问向左侧走4的匹配边4-00仍然已经被访问再向右侧访问0的邻接点即66还未被匹配所以找到增广路径1-4-0-6 3.第1次用匈牙利算法对增广路径1-4-0-6匹配状态取反即1-4变为一对匹配、0-6变成一对匹配。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WKk1Rdbk-1681225850414)(https://img2023.cnblogs.com/blog/824694/202304/824694-20230411230853435-1686292205.png)] 4.第2次找增广路径 再从左侧的2开始先访问到邻接点66已经被访问向左走6的匹配变6-00为左侧的顶点所以0继续向右遍历0的邻接点44已经被访问向左走4的匹配4-11在左侧需要继续向右访问1的邻接点77还未被访问所以我们找到第2条增广路径2-6-0-4-1-7 5.第2次用匈牙利算法对增广路径2-6-0-4-1-7匹配状态取反即2-6变为一对匹配、0-4变成一对匹配、1-7变成一对匹配 6.第3次找增广路径从左侧顶点3出发向右找3的邻接点55未被访问3-5就是一条增广路径7.第3次用匈牙利算法把3-5的匹配状态取反则3-5变成一对匹配边。 8.至此所有的顶点都已被访问找到最大匹配完成(即2-6变为一对匹配、0-4变成一对匹配、1-7变成一对匹配、3-5变成一对匹配一共4对匹配)
起始点从左侧的其他店开始结果是一样地自己可以模拟下
6 匈牙利算法(Hungarian[hʌŋˈɡeriən])的BFS实现
实现代码测试代码本节的算法求解第4节的多米诺骨牌问题
7 匈牙利算法(Hungarian[hʌŋˈɡeriən])的DFS实现
实现代码测试代码使用基于DFS的匈牙利算法重新实现LeetCodeLCP4覆盖问题
