maxbipartitelc.m

图论*匈牙利算法 的两种实现过程 Matching的巧妙在于队列的进入退出并没有仅仅限于在同一层循环中做到

function [n,vm1,vm2]=maxbipartitelc(vc,nv1,nv2)
    if nargin<1
        nv1=5;
        nv2=5;
        vc=[1,1,0,0,0;
            1,0,0,0,0;
            1,0,1,0,0;
            0,0,1,1,1;
            0,0,0,1,1];
    end
    vm1=-ones(1,nv1);
    vm2=-ones(1,nv2);    
	n = 0;
    for i=1:nv1
        q=[];
        qs=1;
        qe=1;
        prev=ones(1,nv2)*(-2);
        for j=1:nv2
            if vc(i,j)
                prev(j)=-1;
                q=[q,j]
                qe=qe+1;
            end
        end
        while qs<qe
            x=q(qs);
            if vm2(x)==-1
                break;
            end
            qs=qs+1;
            for j=1:nv2
                if prev(j)==-2 & vc(vm2(x),j)
                    prev(j)=x;
                    q=[q,j];
                    qe=qe+1;
                end
            end
        end        
        if qs==qe
            continue;
        end
        while prev(x)>-1
            vm1(vm2(prev(x)))=x;
            vm2(x)=vm2(prev(x));
            x=prev(x);            
        end
        vm2(x)=i;
        vm1(i)=x;
        n=n+1;
    end