二分图最大匹配算法的应用及Matlab实现+++

其中前三个文件都是为建立邻接矩阵服务的，Edmonds.m是匈牙利算法的主文件，GUI1.m只是调用Edmonds.m做个界面而已。 调用关系是GUI1.m调用Edmonds.m； Edmonds.m调用BuildMatrix.m和LockMap.m ；LockMap.m调用RecuCal.m 最后运行GUI1.m就ok了

#LockMap.m

function [LMA, LMB] = LockMap(n, m)

% LOCKMAP - 求解满足条件锁并设置相应的映射 % 输入参数:n 表槽数,m 表高度数。

% 输出参数:LMA,LMB 分别为二维矩阵表示自然数到满足条件锁之间的映射。 global jiA ouB ary A B mm N N = n; mm = m; jiA=0; ouB=0; A=[]; B=[];

ary = zeros(1, n); RecuCal(n); LMA=A; LMB=B;

[lena, n] = size(LMA); [lenb, n] =size(LMB); if lena>lenb

temp = LMA; LMA=LMB;LMB=temp; temp = lena;lena=lenb;lenb=temp; end

#RecuCal.m

function RecuCal(n) % RECUCAL - 递归函数

global jiA ouB ary A B mm N if n ==1

for k=1:mm

% 调用递归函数时要用到的变量所以 % 设为全局 ary(1) = k;

Max = max(ary); Min = min(ary); num = 0; neighbor = 0; for i=1:N

num = num + (Max-ary(i))*(ary(i)-Min);

if (i~=N)

neighbor = max(neighbor, abs(ary(i)-ary(i+1))); end end

if (neighbor > mm-1.5)&&(num > 0.5) if mod(sum(ary), 2) % 奇数,属于 A 类 jiA = jiA+1; A(jiA,:) = ary; else

% 偶数,属于 B 类 ouB = ouB+1; B(ouB,:) = ary; end end end else

for k=1:mm

ary(n) = k; RecuCal(n-1); end end

#BuildMatrix.m

function AB = BuildMatrix(LMA, LMB)

% BUILDMATRIX - 建立邻接矩阵,若 i 与 j 之间可以互开则 AB(i,j)=1,否则为 0。 AB = [];

[lena, n] = size(LMA); [lenb, n] =size(LMB); for i = 1:lena for j=1:lenb tmp = 0; for k=1:n

tmp = tmp + abs(LMA(i,k)-LMB(j,k)); end

if tmp == 1

AB(i, j)=1; end end end

#Edmonds.m

function str = Edmonds(n, m)

% EDMONDS - Edmonds 算法寻找完美匹配 str = [];

[LMA, LMB] = LockMap(n, m); AB = BuildMatrix(LMA, LMB); lena = length(LMA); lenb = length(LMB); if lena==0

disp('其中一个分组为空,

无法匹配'); %当 n=m=3 时只有偶数组无奇数组, 不能完成 匹配 return; end

MatA = zeros(1, lena); MatB = zeros(1, lenb); X = MatA; Y=MatB; Z=Y; NumNoMat = 0;

% 无法匹配的点的个数 % 最初匹配,只有一个匹配 j = find(AB(1,:), 1); MatA(1)=j; MatB(j)=1;

while length(find(MatA==0)) ~= 0 % 存在不匹配的元素

J = find(MatA==0); i = J(1); % 第 i 个元素未被匹配 init = i; X(i)=0; J = find(AB(i,:));

% J 为所有与 i 相邻结点 Y(J) = i; j=J(1);

while ~isempty(find(Y~=Z)) if MatB(j) ~= 0 % j 是匹配点 Z(j) = Y(j); i = MatB(j); X(i)=j;

J = find(AB(i,:)); Y(J)=i;

J = find(Y); JJ = find(Z);

J = setxor(intersect(J, JJ), J); j=J(1); else

% j 不是匹配点 i = Y(j); MatA(i) = j; MatB(j) = i; while X(i) j = X(i); i = Z(j); MatA(i) = j; MatB(j) = i; end break; end end

% 如果 Y==Z 则表明该点没有与之相应的匹配,即不存在完美匹配,在 MatA 中标 % 记为-1。

if isempty(find(Y~=Z, 1)) NumNoMat = NumNoMat + 1; MatA(init) = -1; end

X(1:lena)=0; Y(1:lenb)=0; Z=Y; end

total = 0; for i=1:lena k = MatA(i);

if k<=0 continue; end % k<=0 时表明匹配不存在 stra = ''; strb = ''; for j=1:n

stra = [stra, num2str(LMA(i, j)), ' ']; strb = [strb, num2str(LMB(k, j)), ' ']; end

str = [str, stra, '------ ', strb, 10]; total = total + 1; end

str = [str, '匹配个数有:', num2str(total)];

#GUI1.m

function varargout = GUI1(varargin) gui_Singleton = 1;

gui_State = struct('gui_Name', mfilename, ...

'gui_Singleton', gui_Singleton, ...

'gui_OpeningFcn', @GUI1_OpeningFcn, ... 'gui_OutputFcn', @GUI1_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []);

if nargin && ischar(varargin{1})

gui_State.gui_Callback = str2func(varargin{1}); end

if nargout

[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); else

gui_mainfcn(gui_State, varargin{:}); end

% End initialization code - DO NOT EDIT

% --- Executes just before GUI1 is made visible.

function GUI1_OpeningFcn(hObject, eventdata, handles, varargin) handles.output = hObject; guidata(hObject, handles);

function varargout = GUI1_OutputFcn(hObject, eventdata, handles) varargout{1} = handles.output;

function pushbutton1_Callback(hObject, eventdata, handles) a = get(handles.edit1, 'String'); b = get(handles.edit2, 'String');

str = Edmonds(str2num(a), str2num(b)); set(handles.edit4, 'String', str); guidata(hObject, handles);

function edit1_Callback(hObject, eventdata, handles) input = str2num(get(hObject, 'String')); guidata(hObject, handles);

function edit1_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end

function edit2_Callback(hObject, eventdata, handles) input = str2num(get(hObject, 'String')); guidata(hObject, handles);

function edit2_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end

function slider1_Callback(hObject, eventdata, handles) function slider1_CreateFcn(hObject, eventdata, handles) if isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor',[.9 .9 .9]); end

function text_result_Callback(hObject, eventdata, handles) function text_result_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end

function edit4_Callback(hObject, eventdata, handles) function edit4_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end

function pushbutton2_Callback(hObject, eventdata, handles) set(handles.edit4, 'String', ''); set(handles.edit1, 'String', ''); set(handles.edit2, 'String', '');