maxbipartitematching.m

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

function MaxBipartiteMatching(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=[4,5;8,9];
        Q=[1,2,3];
        plotmatch(V,U,E,M)
    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]]
                    plotmatch(V,U,E,M)
                    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)];
                        plotmatch(V,U,E,M)
                        v=F(u);
                        if isempty(find(v==V))
                            M=[M,[u;v]]
                        else
                            M=[M,[v;u]]
                        end
                        plotmatch(V,U,E,M)
                    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)