fulkerson.m

10组图论编程

function [f,flow]=fulkerson(u,s,t)
%s是流起始点，t是流终结点。
M=1000; 
%u是图的容量矩阵。 
if nargin<1
u(1,2)=1;u(1,3)=1;u(1,4)=2; 
u(2,3)=1;u(2,5)=2; 
u(3,5)=1; 
u(4,3)=3;u(4,5)=3;
u(5,1:5)=0;
end
if nargin<2
    s=2;
    t=5;
end
%f是现有的流量矩阵。
f=zeros(size(u));
n=length(u); 
list=[]; 
flow=[];%最大流。
maxf=zeros(1:n);maxf(t)=1; 
while maxf(t)>0 
   maxf=zeros(1,n);pred=zeros(1,n); 
   list=s;record=list;maxf(s)=M; 
   while (~isempty(list))&(maxf(t)==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(t)>0 
         v2=t; 
         v1=pred(v2); 
         while v2~=s
           if v1>0 
              f(v1,v2)=f(v1,v2)+maxf(t); 
          else 
           v1=abs(v1); 
           f(v2,v1)=f(v2,v1)-maxf(t); 
       end 
         v2=v1; 
         v1=pred(v2); 
     end 
 end 
 end 
flow=sum(f(s,:));
f
flow
end