python最长匹配_二分图最大匹配：匈牙利算法的python实现

二分图匹配是很常见的算法问题，一般用匈牙利算法解决二分图最大匹配问题，但是目前网上绝大多数都是C/C++实现版本，没有python版本，于是就用python实现了一下深度优先的匈牙利算法，本文使用的是递归的方式以便于理解，然而迭代的方式会更好，各位可以自行实现。

1、二分图、最大匹配

什么是二分图：二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

匈牙利算法应用、什么是匹配：把上图想象成3位工人和4种工作，连线代表工人愿意从事某项工作，但最终1个工人只能做一种工作，最终的配对结果连线就是一个匹配。匹配可以是空。

什么是最大匹配：在愿意从事的基础上，能够最多配成几对。

现在要用匈牙利算法找出最多能发展几对。

[color=green][size=medium]

匈牙利规则，匈牙利算法是解决寻找二分图最大匹配的。

更多二分图最大匹配的图解可以参考 http://xuxueliang.blog.51cto.com/5576502/1297344

以下是代码，为了图省事使用了类，实际上并不需要这样

M=[]classDFS_hungary():def __init__(self, nx, ny, edge, cx, cy, visited):

匈牙利路径算法。self.nx, self.ny=nx, ny

self.edge=edge

self.cx, self.cy=cx,cy

self.visited=visiteddefmax_match(self):

匈牙利超越？res=0for i inself.nx:if self.cx[i]==-1:

for key in self.ny: #将visited置0表示未访问过

self.visited[key]=0

res+=self.path(i)returnresdefpath(self, u):for v inself.ny:if self.edge[u][v] and (notself.visited[v]):

大匈牙利、self.visited[v]=1

if self.cy[v]==-1:

self.cx[u]=v

self.cy[v]=u

python编程，M.append((u,v))return 1

else:

M.remove((self.cy[v], v))ifself.path(self.cy[v]):

self.cx[u]=v

python3、self.cy[v]=u

M.append((u, v))return 1

return 0

ok，接着测试一下：

python找最长的字符串？if __name__ == '__main__':

nx, ny= ['A', 'B', 'C', 'D'], ['E', 'F', 'G', 'H']

edge= {'A':{'E': 1, 'F': 0, 'G': 1, 'H':0}, 'B':{'E': 0, 'F': 1, 'G': 0, 'H':1}, 'C':{'E': 1, 'F': 0, 'G': 0, 'H':1}, 'D':{'E': 0, 'F': 0, 'G': 1, 'H':0}} # 1 表示可以匹配， 0 表示不能匹配

cx, cy= {'A':-1,'B':-1,'C':-1,'D':-1}, {'E':-1,'F':-1,'G':-1,'H':-1}

python字符串最大长度、visited= {'E': 0, 'F': 0, 'G': 0,'H':0}print DFS_hungary(nx, ny, edge, cx, cy, visited).max_match()

结果为4，是正确的。各位也可以使用其它二分图来测试。

---------------------------------------------------------补充BFS版本匈牙利算法-------------------------------------------------------

BFS版本的匈牙利算法性能更好一些，但是比较难理解，下面把BFS版本的算法也贴出来，也是翻译自c++版本，这次使用更好的迭代方式替换了递归方式

Python字符串最长。defBFS_hungary(g,Nx,Ny,Mx,My,chk,Q,prev):

res=0for i inxrange(Nx):if Mx[i]==-1:

qs=qe=0

Q[qe]=i

qe+=1prev[i]=-1flag=0while(qs

u=Q[qs]for v inxrange(Ny):if flag:continue

if g[u][v] and chk[v]!=i:

chk[v]=i

Q[qe]=My[v]

qe+=1

if My[v]>=0:

prev[My[v]]=uelse:

flag=1d,e=u,vwhile d!=-1:

t=Mx[d]

Mx[d]=e

My[e]=d

d=prev[d]

e=t

qs+=1

if Mx[i]!=-1:

res+=1

return res

测试一下:

if __name__ == '__main__':

g=[[1,0,1,0],[0,1,0,1],[1,0,0,1],[0,0,1,0]]

Nx=4Ny=4Mx=[-1,-1,-1,-1]

My=[-1,-1,-1,-1]

chk=[-1,-1,-1,-1]

Q=[0 for i in range(100)]

prev=[0,0,0,0]print BFS_hungary()

结果为4,正确