图论算法-最大流算法和最大匹配算法

图论算法-最大流算法和最大匹配算法

最大流算法

clc,clear,M=1000; c(1,2)=3;c(1,4)=3; c(2,3)=1;c(2,4)=20; c(3,6)=3; c(4,5)=10;

c(5,1)=4;c(5,3)=2;c(5,6)=13; n=length(u); list=[];

maxf=zeros(1:n);maxf(n)=1; while maxf(n)>0

maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; index1=(find(u(flag,:)~=0));

label1=index1(find(u(flag,index1)... -f(flag,index1)~=0));

label1=setdiff(label1,record); list=union(list,label1);

pred(label1(find(pred(label1)==0)))=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1));

record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2';

label2=setdiff(label2,record); list=union(list,label2);

pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end

if maxf(n)>0 v2=n;

v1=pred(v2); while v2~=1 if v1>0

f(v1,v2)=f(v1,v2)+maxf(n); else

v1=abs(v1);

f(v2,v1)=f(v2,v1)-maxf(n); end v2=v1; v1=pred(v2);

end end end f

function [f,wf,No]=MaxFlowMinCut_Me(n,C)% f %显示最大流

% 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码

% wf %显示最大流量% n 节点个数% C %弧容量

% No %显示标号, 由此可得最小割

最大流算法

for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号while(1)

No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程

for(i=1:n)if(No(i)) %选择一个已标号的点viNo(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)>d(i))d(j)=d(i);end

for(j=1:n)if(No(j)==0&f(i,j)

elseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;

if(d(j)>d(i))d(j)=d(i);end;end;end;end;end

if(No(n)|pd)break;end;end %若收点vt 得到标号或者无法标号, 终止标号过程if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt 表示调整量while(1)

if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整

elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧调整t=No(t);end;end; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end

if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %当t 的标号为vs 时, 终止调整过程

end

n=6;

C=[0 3 0 3 0 0

0 0 1 20 0 0 0 0 0 0 0 3 0 0 0 0 10 0 0 4 2 0 0 13 0 0 0 0 0 0];

[f,wf,No]=MaxFlowMinCut_Me(n,C) 最大匹配算法

A=[1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1]; A=[1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1]; A=[1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1]; A=[1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1]; A=[1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1];

m=5;n=5;M(m,n)=0;

for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end %求初始匹配M if(M(i,j))break;end;end %获得仅含一条边的初始匹配M while(1)

for(i=1:m)x(i)=0;end %将记录X中点的标号和标记*

for(i=1:n)y(i)=0;end %将记录Y中点的标号和标记* for(i=1:m)pd=1; %寻找X中M的所有非饱和点 for(j=1:n)if(M(i,j))pd=0;end;end

if(pd)x(i)=-n-1;end;end %将X中M的所有非饱和点都给以标号0 和标记*, 程序中用n+1 表示0 标号, 标号为负数时表示标记* pd=0; while(1)xi=0;

for(i=1:m)if(x(i)<0)xi=i;break;end;end %假如X 中存在一个既有标号又有标记*的点, 则任取X中一个既有标号又有标记*的点xi

if(xi==0)pd=1;break;end %假如X中所有有标号的点都已去掉了标记*, 算法终止 x(xi)=x(xi)*(-1); %去掉xi 的标记* k=1;

for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;end %对与xi 邻接且尚未给标号的yj 都给以标号i

if(k>1)k=k-1; for(j=1:k)pdd=1;

for(i=1:m)if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break;end;end %将yj 在M中与之邻接的点xk (即xkyj∈M), 给以标号j 和标记* if(pdd)break;end;end

if(pdd)k=1;j=yy(j); %yj 不是M的饱和点

while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j))); %任取M的一个非饱和点yj, 逆向返回 if(j==n+1)break;end %找到X中标号为0 的点时结束, 获得M-增广路P k=k+1;end

for(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0; %将匹配M 在增广路P 中出现的边去掉 else M(P(i,1),P(i,2))=1;end;end %将增广路P 中没有在匹配M中出现的边加入到匹配M中 break;end;end;end

if(pd)break;end;end %假如X中所有有标号的点都已去掉了标记*, 算法终止 M %显示最大匹配M, 程序结束

利用可行点标记求最佳匹配算法的 MATLAB 程序代码如下： n=5; A=[3 5 5 4 1 2 2 0 2 2 2 4 4 1 0 0 1 1 0 0 1 2 1 3 3];

for(i=1:n)L(i,1)=0;L(i,2)=0;end

for(i=1:n)for(j=1:n)if(L(i,1)