maxbimatching.m

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

function M=MaxBiMatching(V,U,E,M,Q)
% Introduction to the Design and Analysis of Algorithms Page279
    if nargin<1
        clc;clear;
        V=[1,2,3,4,5];
        U=[6,7,8,9,10];
        E=[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];
        M=[];
        Q=[1,2,3,4,5];
        plotmatch(V,U,E,M)
        pause(1)
    end

    % pre-processing end
    F=zeros(1,length(V)+length(U));
    while ~isempty(Q)
        w=Q(1);
        Q=Q(2:end);
        wiV=find(w==V);
        if ~isempty(wiV)
            for k=1:length(U)
                if E(wiV,k) % each connect point by w
                    u=U(k);
                else
                    continue
                end

                if isempty(find(u==M))% if u is spare point
                    M=[M,[w;u]];
                    v=w;
                    while F(v)>0
                        u=F(v);
                        for k=1:size(M,2)
                            if M(1,k)==v & M(2,k)==u
                                break
                            end
                        end
                        M=[M(:,1:k-1),M(:,k+1,end)];
                        v=F(u);
                        if isempty(find(v==V))
                            M=[M,[u;v]];
                        else
                            M=[M,[v;u]];
                        end                        
                    end
                    F=zeros(1,length(V)+length(U));
                    Q=[];
                    for k=1:length(V)
                        if isempty(find(V(k)==M))
                            Q=[Q,V(k)];
                        end
                    end
                    break
                else
                    Fwuin=1;
                    for k=1:size(M,2)
                        if M(1,k)==w & M(2,k)==u
                            Fwuin=0;
                            break
                        end
                    end
                    if Fwuin & ~F(u)
                        F(u)=w;
                        if isempty(find(u==Q))
                            Q=[Q,u];
                        end                        
                    end
                end
            end
            
        else % w in U
            Mt=M(2,:);
            kM=find(w==Mt);
            u=M(1,kM);
            F(u)=w;
            if isempty(find(u==Q))
                Q=[Q,u];
            end              
        end
    end
    M;
    plotmatch(V,U,E,M);