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

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

最大流算法

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);