算法笔记【6】匈牙利算法简介http://www.Sina.com/(http://www.Sina.com/)。 匈牙利算法主要用于解决与二分图匹配**相关的问题，所以我们先来看看二分图。
3358 www.Sina.com/(http://www.Sina.com/)为特殊的http://www.Sina.com/，分为两部分，每个部分内的点互不相连。 下图是典型的二分图。
在上面的二分图中，可以看到每一边的端点分别位于点集x和y中。 匈牙利算法主要用于解决求二分图的3358www.Sina.com/和今天我们来看一个没有前几篇讲的那么常用，但是很有用的算法：匈牙利算法两个问题。
这样太抽象了。 我们现在从实际问题出发。
最大的匹配问题读了上述，相信读者在云上的雾中。 这是什么？ 这有什么用？ 所以我们把这张二分图做点手脚，如下。
现在，单纯的奥特曼和女孩分别是两套，里面的分分别是男生和女生，说明他们之间有“暧昧关系”。 最大的匹配问题是Hungarian algorithm(数学表示；在二分图中最多可以找到多少条没有共同端点的边) ) ) ) ) ) ) ) )。
看看匈牙利算法的工作原理：
我们从B1来看(男女平等，也可以从女性方面来看)，他和G2很模糊，所以我们先把他连接到G2上)。此时，请注意，你只是作为红娘在纸上设想，你并没有真正行动。 此时的安排都是暂时的)。
来看B2，B2也喜欢G2。 此时，G2已经成为“名花有主”(虽然只是我们设想的)。 我们回去看看G2现在安排的男朋友，是B1。 B1还有其他选择吗？ 是的，G4、G4还没有安排。 在B1上安排G4。
然后B3、B3直接与G1配合就可以了，但这没有任何问题。 关于B4，只迷上了G4，G4中现在掺入了B1。 B1除了G4以外，还可以选择G2，怎么样？如果B1选择了G2，就不能选择G2的jqdlmB2。 我们绕了一大圈，发现B4注定是单身。 真可怜。 (实际上，前所未有的G3更可怜)
这就是匈牙利算法的流程。 有关具体实现，请查看代码：
public class arithmetic6{ publicstaticvoidmain (string [ ] args ) int [ ] map=new int [ ] { 1，1，0，0 } 1，0，0，0，0，1 }，1 Hungarian Hungarian=new Hungarian (map； int Hungarian1=Hungarian.Hungarian (； system.out.println(Hungarian1； }静态类别Hungarian { int m，n； //M，n分别是左右集合的要素数int[][] map； //相邻矩阵保存图int[] p； //与当前右侧元素相对应的左侧元素boolean[] vis； //右侧元素为公共Hungarian (int [ ] [ ] map ) { this.m=map.length； this.n=map[0].length； this.map=map； this.p=new int[n]； this.vis=new boolean[n]； }布尔匹配(inti，int b ) (for ) int b； j n； j () if ) map[I][j]！=0) /右边的第j个号码递归地去找匹配p[j]的对象，但其他可以匹配的if(vis[j] ) if (match ) p[j]，j 1) ) p[j]； 返回真； } } else { //不匹配而vis[j]=true； p[j]=i； 返回真； } }返回假； } public int hungarian (() { int cnt=0； for(intI=0； i m； I ) if (匹配(I，0 ) ) CNT； } }返回CNT； }}其实过程与我们的上述一致。 请注意，这里使用的是递归技巧。 我们不断向下递归，试着寻找合适的匹配。
最小点覆盖问题另一个关于二分图的问题是求二分图。 我们想找到Bipartite graph的几个图，让二分图的每一边都是http://www.Sina.com。反过来说，包含这些点的埃
这为什么能用匈牙利算法解决呢？ 如果你以为我会争论很久，那就错了。 我们只需要一个定理：
最大匹配数
一个二分图中的最大匹配数最小点覆盖数此图中的最小点覆盖数
好了，这个节结束。 我们不是在做数学，所以不需要证明。 如果你感兴趣的话，请参考这个博客。 愚蠢的我不理解)。 但是，它提供了一种在视觉上查找最小点集的方法。 查看上一节最后一张图(或问题图)，从左侧的假如你是红娘，可以撮合任何一对有暧昧关系的男女，那么你最多能成全多少对情侣查看匈牙利算法流程(即紫色箭头)，查看所有最小点覆盖和http://ww.Sina.com
-----------------感谢您最后一次阅读。 希望大家的技术越来越少。 -----------------
-----------------也请大家支持。 谢谢您的伟大。 -----------------