匈牙利算法 二分图匹配 matlab代码
匈牙利算法 二分图匹配 matlab代码
最近学习了一下匈牙利算法，写了个拙劣的代码
希望可以和大家交流
程序是基于增广路径方法的递归结构
- 算法流程图
- 代码
%% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % 信息说明 % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
%% 程序说明
%{
Author：暮烟暮烟
Date：2020.11.11匈牙利算法找到二分图G=(V,E)的最大匹配M
V=X+Y，X有n个顶点，Y包含m个顶点
仅在主程序中可以更新M和num_M
子程序仅仅得到增广路径
%}
%% 输入变量说明
%{
效率矩阵C=n*m=[0 1 0 1 1 0;1 1 0 0 0 0;0 1 0 0 0 1;0 0 0 1 1 0;0 1 1 0 0 0;]
%}
%% 输出变量说明
%{
M：图G的最大匹配M（实际应用中一般也是完美匹配）
num_M：最大匹配数
%}
%% 关键变量说明
%{
X：X顶点匹配标识向量
*_X：X中顶点的位置下标
Y：Y顶点匹配标识向量
*_Y：Y中顶点的位置下标
P：M-增广路径
%}
%% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % %% % 主程序代码部分 % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
%% 主程序
% ===============================初始化参数=================================
clear all;
C = [0 1 0 1 1 0;1 1 0 0 0 0;0 1 0 0 0 1;0 0 0 1 1 0;0 1 1 0 0 0;];
[n,m] = size(C);
M = zeros(n,m);
X = zeros(1,n);
Y = zeros(1,m);
num_M = 0; %最大匹配数% ==================================遍历Xi=================================
for i_X=1:nP = zeros(n,m); %清空增广路径%===============================遍历Yj================================= for j_Y=1:m%------------------Yj和Xi是连接点 且 Yj未匹配------------------------if (C(i_X,j_Y))&&(~max(M(:,j_Y)))%找到新匹配Xi-Yj 有增广路径 最大匹配+1P(i_X,j_Y) = 1;X(i_X) = 1;Y(j_Y) = 1;M = xor(M,P);num_M = num_M+1;%-----------------Yj和Xi是连接点 且 Yj已经匹配-----------------------elseif (C(i_X,j_Y))&&(max(M(:,j_Y)))u_X = find(M(:,j_Y));%找到与Yj匹配的顶点Xu%----------------Xu是否可以和其它顶点匹配------------------------[P,X,Y] = DfsFun(u_X,j_Y,X,Y,C,M,P);if ~Y(j_Y)%Xn可以和其它顶点匹配 释放Yj%找到新匹配Xi-Yj 有增广路径 最大匹配+1P(i_X,j_Y) = 1;X(i_X) = 1;Y(j_Y) = 1;M = xor(M,P);%异或得到新Mnum_M = num_M+1;end%Xu不可以和其它点匹配 进入下一个Y的循环end %Yj和Xi不是连接点 进入下一个Y的循环%-----------------------Xi找到匹配 跳出循环--------------------------if X(i_X)break;endend
end%=====================输出最大匹配M和最大匹配数num_M=========================
M
num_M%% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % 局部函数代码部分 % % % % % % % % % % % %% % %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
%% 局部函数DfsFun
function [P,X,Y] = DfsFun(u_X,j_Y,X,Y,C,M,P)
%Xu是否能找到Yj以外的匹配
%由Y(j_Y)表示 0代表找到 1代表未找到%==================================参数初始化===============================
[n,m] = size(M);
% P = zeros(n,m);
P(u_X,j_Y) = 1;%=================================遍历Yj以外的Y=============================
%----------------------------------确定v_Y取值------------------------------
if j_Y==1v_Y = 2:m;
elseif j_Y==mv_Y = 1:m-1;
elsev_Y = [1:j_Y-1,j_Y+1:m];
endfor v_Y=v_Y%-----------------------Yv是Xu的连接点 且Yv未匹配------------------------if (C(u_X,v_Y))&(~M(:,v_Y))%找到新匹配 原本的Yj-Xu 换为Xu-Yv和Yj-Xi Y(v_Y) = 1;Y(j_Y) = 0;%释放YjP(u_X,v_Y) = 1;%----------------------Yv是Xu的连接点 且Yv已经匹配Xk---------------------elseif (C(u_X,v_Y))&&(max(M(:,v_Y)))k_X = find(M(:,v_Y));%找到与Yv匹配的顶点Xk%----------------Xk是否可以和其它顶点匹配------------------------[P,X,Y] = DfsFun(k_X,v_Y,X,Y,C,M,P);%Xk可以和其它顶点匹配if Y(v_Y)==0 %释放YvY(v_Y) = 1;Y(j_Y) = 0;P(u_X,v_Y) = 1;end %Xk不可以和其它点匹配 进入下一个Y的循环end %Yv和Xu不是连接点 进入下一个Y的循环%------------------------Xu找到Yj以外的匹配 跳出循环---------------------if ~Y(j_Y)break;end
end
end
希望大家多多交流提意见啊，喵
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！