g:array[1..maxn,1..maxm]of boolean; y:array[1..maxm]of boolean; link:array[1..maxm]of longint; function find(v:longint):boolean; var i:longint; begin
for i:=1 to m do
if g[v,i] and (not y[i]) then begin y[i]:=true;
if (link[i]=0)or find(link[i]) then begin link[i]:=v; find:=true; exit; end; end;
find:=false; end; begin
//read the graph into array g[][] for i:=1 to n do begin
fillchar(y,sizeof(y),0); if find(i) then inc(ans); end;
我用C++的,这个PASCAL程序是别处的
其中n,m分别为2部图两边节点的个数,两边的节点分别用1..n,1..m编号 g[x][y]=true表示x,y两个点之间有边相连 link[y]记录的是当前与y节点相连的x节点 y[i]记录的是y中的i节点是否被访问过.
算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条\交错轨\也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行\反色\容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.
代码中find(i)就是寻找有没有从x点i开始的增广轨,如果有就进行上述操作,代码是递归的,所以看起来不是很显然,画个图试试就很清楚了.
P.S. 我比较笨,以前学习匈牙利算法时花了不少时间来理解这段代码的意思,希望楼主能很快理解,所以用很贫乏和不规范的语言描述了一下算法.希望能满意