二分图最大匹配---匈牙利算法（Hungarian Algorithm）
一、相关概念 1、二分图（bipartite graph）
百度百科上的定义：二分图又称作二部图， 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
通俗地说：把一个图的顶点划分为两个不相交集合 U和 V ，使得每一条边都分别连接U 、 V中的顶点。如果存在这样的划分，则此图为一个二分图。图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。
文章图片
文章图片
文章图片
文章图片
2、匹配·（matching）
匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，上图中的图 3、图 4 中红色的边就是图 2 的匹配。
3、最大匹配
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。图 4 是一个最大匹配，它包含 4 条匹配边。
4、完美匹配
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。
举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。
文章图片
二、匈牙利算法（Hungarian Algorithm）-------求解最大匹配问题 
文章图片
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
增广路：从一个未匹配的点开始，依次走过未匹配边，匹配边，未匹配边，匹配边，。。。。。。 如果最后的终点是一个未匹配点（即最后一条边是一条未匹配边），那么这条路就是一条增广路。而将增广路上的未匹配边和匹配边进行互换，就会使得匹配边多一条。
例如，图 5 中的一条增广路如图 6 所示（图中的匹配点均用红色标出）：
文章图片
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。
匈牙利算法思想：该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法
注：以下转自 http://blog.csdn.net/dark_scope/article/details/8880547（比较好理解）
通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异性有好感，如果一对男女互有好感，那么你就可以把这一对撮合在一起，你拥有的大概就是下面这样一张关系图，每一条连线都表示互有好感。
文章图片
本着救人一命，胜造七级浮屠的原则，你想要尽可能地撮合更多的情侣，匈牙利算法的工作模式会教你这样做：
===============================================================================
一： 先试着给1号男生找妹子，发现第一个和他相连的1号女生还名花无主，got it，连上一条蓝线
文章图片
===============================================================================
二：接着给2号男生找妹子，发现第一个和他相连的2号女生名花无主，got it
文章图片
===============================================================================
三：接下来是3号男生，很遗憾1号女生已经有主了，怎么办呢？
我们试着给之前1号女生匹配的男生（也就是1号男生）另外分配一个妹子。
(黄色表示这条边被临时拆掉)
文章图片
与1号男生相连的第二个女生是2号女生，但是2号女生也有主了，怎么办呢？我们再试着给2号女生的原配()重新找个妹子(注意这个步骤和上面是一样的，这是一个递归的过程)
文章图片
此时发现2号男生还能找到3号女生，那么之前的问题迎刃而解了，回溯回去
2号男生可以找3号妹子~~~1号男生可以找2号妹子了~~~3号男生可以找1号妹子
文章图片
文章图片
文章图片
所以第三步最后的结果就是：
文章图片
===============================================================================
四： 接下来是4号男生，很遗憾，按照第三步的节奏我们没法给4号男生腾出来一个妹子，我们实在是无能为力了
===============================================================================
这就是匈牙利算法的流程，其中找妹子是个递归的过程，最最关键的字就是“腾”字
匈牙利算法的另一个案例:（理解思想）
1、起始没有匹配
文章图片
2、选中第一个x点找第一跟连线
【二分图最大匹配---匈牙利算法（Hungarian Algorithm）】
文章图片
3、选中第二个点找第二跟连线
文章图片
4、发现x3的第一条边x3y1已经被人占了，找出x3出发的的交错路径x3-y1-x1-y4，把交错路中已在匹配上的边x1y1从匹配中去掉，剩余的边x3y1 x1y4加到匹配中去
文章图片
5、同理加入x4,x5。
匈牙利算法可以深度有限或者广度优先，本文的示例采用深度优先，即x3找y1,y1已经有匹配，则找交错路。若是广度优先，应为：x3找y1,y1有匹配，x3找y2。
python代码实现：
#匈牙利算法求解最大匹配问题
def Matching(u):
for i in range(1,m+1):#扫描B集合的每个顶点
if Graph[u][i]==1 and used[i]==0:#x与i之间有边，并且i未被访问
used[i]=1
if B[i]==0 or Matching(B[i]):#i未被匹配，或者通过i节点可以找到增广路
B[i]=u
return Truereturn Falsewhile True:
k,n,m=eval(input("\n请输入三个数以逗号隔开，分别代表边的个数、A集合元素个数、B集合元素个数："))
Graph=[[0 for e in range(0,m+1)] for j in range(0,n+1)]#存储图
print("请输入k行，每行两个整数以逗号隔开，表示一条边")
for i in range(0,k):
a,b=eval(input())
Graph[a][b]=1
#print(Graph)
B=[0 for i in range(0,m+1)]#用来存储B匹配的对象
used=[0 for i in range(0,m+1)]
ans=0
for i in range(1,n+1):
used=[0 for i in range(0,m+1)]#每次匹配前都清零
if Matching(i):
ans=ans+1print("最大匹配是：",ans)
