在学习KM算法前，我们先感受一下匈牙利算法（由匈牙利数学家Edmonds提出）。
匈牙利算法 解决何种问题的呢匈牙利算法是解决二分图的最大匹配度问题。
何为二分图如果用染色法来判断的话，那么整幅图最后只会有两种颜色的元素；所谓二分图，就是可以划分为两个集合，且同一集合中的元素是互不相连的，不同集合中的元素是可以相连的。
下面我们通过一个简单的例子来说明：现在有家公司，有三个员工和三种工作，员工与工作相连表示员工可以胜任这份工作
匈牙利算法解决的就是如何让更多的员工胜任不同的工作,在本题中可以直接看出来结果，但 算法的作用就是让复杂的问题模板化，任何算法的给出都是为了规整化一个问题的解决步骤，其目的是为了在问题规模越来越大时算法对其仍然适用。
首先，对员工A 我们对其匹配工作a，
此后，对员工B 他第一个匹配的是工作a，但我们刚才才将a匹配给了A，这时，我们就需要用到匈牙利算法，**“匈牙利算法”指出 通过一条增广路径，通过取反操作，我们就能匹配更多的点。**
什么是增广路径
由未匹配的节点开始，到未匹配的节点结束，路经若干个匹配的节点。
1. **一前一后两个节点一定是还未匹配的节点**
2. **将增广路径取反后就可以得到一个更大的匹配**
3. **当找不到其他的增广路径就说明当前匹配最大**
如下图，我们找到一条增广路径 B-->a-->A-->c
如何对增广路径进行取反
增广路径B-->a-->A-->c，红色表示在匹配中的节点，黑色表示未在匹配中的节点。增广路径的取反就是将在匹配中的节点拿出，将未在匹配中的节点放进去。 B-->a-->A-->c，于是，我们重新分配如下图：
对于员工C，他匹配的也是c,这时我们再次找一条增广矩阵，
增广路径： C-->c-->A-->a-->B-->b，取反：C-->c-->A-->a-->B-->b
就算集合中的元素很多很多，我们仍能通过匈牙利算法得到该二分图的最大匹配。
KM算法下面我们考虑如果每个员工做每件工作的效率是不同的，我们如何让整个公司的工作效率最高呢
这种问题称为带权二分图的最有匹配问题，可以用KM算法解决。
当然，如果不了解KM算法，还是可以用匈牙利算法来解决，可以把所有的最优匹配找出来，然后计算总权值，最后取总权值最大的那个匹配。但这样的话可以解决一小部分数据量不太大的问题，最有效的还是用KM算法来解决。
KM 算法解决步骤：
先将左边的顶点赋值为权重最大，右边的顶点赋值为0进行匹配，匹配原则：只匹配相同权重的边，如果没有此边，则在这条路径上的所有点，左边点-1，右边点+1，直到匹配成功为止。
对于A，我们匹配Ac（4+0=4）；对于B，我们匹配Bc（3+0=3），但c是已经匹配过了，所以我们要考虑将A或者B换一个来匹配，此时我们涉及到的点有 A B c，故 左边的A B -1，右边的c+1
这时我们发现，A多了一条可匹配边a，B可匹配a，故A-->c B-->a
接下来我们对C进行匹配，发现C没有可以匹配的边，故C-1
于是呢 C就可以和c匹配，但c已经和A匹配了，于是去找A，A本来还可以和a匹配，但是a又被B给匹配了，所以又去找B，而B现在呢没有边可以匹配了（2+0！=1），故路径 C-->c-->A-->a-->B左边顶点-1，右边顶点+1
对B来b可以匹配，
用匈牙利算法对这条路径进行取反，
如图，便完成了此题的最终匹配。
整体思路就是：每次都帮一个顶点匹配最大权重边，利用匈牙利算法完成最大匹配，最终我们完成的就是最优匹配！