maxbipartite.m

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

function [n,vm1,vm2]=maxbipartite(vc,nv1,nv2) %int Bipartite(bool vc [][MAX],int nv1,int nv2) 
    clc
    if nargin<1
        nv1=5;
        nv2=5;
        vc=zeros(nv1,nv2);
        vc(1,2)=1;
        vc(1,3)=1;
        vc(1,4)=1;
        vc(2,1)=1;
        vc(2,2)=1;
        vc(2,5)=1;
        vc(3,2)=1;
        vc(3,3)=1;
        vc(3,4)=1;
        vc(4,3)=1;
        vc(5,1)=1;
%         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];
        posi1=1:5;
        posi2=1:5;
        hold on
        for i=1:5
            for j=1:5
                if vc(i,j)
                    plot([posi1(i),posi2(j)],[1,0]);
                end
            end
        end
    end
% vc 邻接矩阵
	vm1=-ones(1,nv1);
    vm2=-ones(1,nv2);    
	n = 0;

    for i=1:nv1
        i
        q=[];
        prev=ones(1,nv2)*(-2);
        qs=1
        qe=1
        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;
        vm1
        vm2
    end
    n
    figbipart(vm1,vm2)
    
    
    function figbipart(vm1,vm2)
        posi1=1:5;
        posi2=1:5;
        hold on
        for i=1:length(vm1)
            plot([posi1(i),posi2(vm1(i))],[1,0],'r')
        end