www.gusucode.com > 里面有最大流，最小费用最大流和着色问题的matlab程序和lingo程序 > 里面有最大流，最小费用最大流和着色问题的matlab程序和lingo程序/最大流，最小费用流，着色程序/ford最大流.m

    function [f,wf,T]=ford(C)
%Ford-Fulkerson算法（双向调整法），求容量网络的最大流(1--> n)
%C=[0 5 4 3 0 0 0 0
 %  0 0 0 0 5 3 0 0
 %  0 0 0 0 0 3 2 0
 %  0 0 0 0 0 0 2 0
 %  0 0 0 0 0 0 0 4
 %  0 0 0 0 0 0 0 3
 %  0 0 0 0 0 0 0 5
 %  0 0 0 0 0 0 0 0];%容量网络
n=length(C);s=1;
f=zeros(size(C));%取初始可行流为零流
while(s)%找到增大流量的一条路
    flag1=1;
    T=1;%从发点向收点搜索时形成的有序树
    L1(1)=inf;%L1(v)为T上唯一的路1--v（记为P）的容量，希望搜索到L(n)
    L2(1)=1;%L2(v)为P上v的父顶点
    R=[];%T中已生长完成的顶点（当前点以前被搜索过的点）
    while(flag1)%有多个生长点时，一个没有后继顶点就改变到另一个
    T_R=setdiff(T,R);s=length(T_R);%取差集
    if s==0%没有向后搜索有容量的路了，结束，此时割（T,Tc）为最大割
        wf=0;
        for j=1:n
            wf=wf+f(1,j);%求总流量
        end
        break;
    end
    u=T_R(1);%往后搜索有多个生长点取第一个
    while(1)%有后继顶点往后搜索
    Tc=setdiff(1:n,T);%T的补，在这里面找u往后的子顶点
    N=C-f;N=N+f';%得到伴随网络（有容量的可以继续流，有流量的可以倒回去）
    for k=1:length(Tc)
        flag=1;%如果找不到后继顶点，将作为返回的标记
        v=Tc(k);
        if N(u,v)>0
            flag=0;%找到了后继顶点
            T=union(T,v);
            L1(v)=min(L1(u),N(u,v));
            if f(v,u)>0%说明u-->v是反向边
               L2(v)=-u;
           else%说明u-->v是正向边（反向边一定要有流量才能倒回去）
               L2(v)=u; 
           end
           if v==n
               m=n;
              while(m~=1) %逆向追踪求1-->n的路，调整流量
                  t=abs(L2(m));
                  f(t,m)=f(t,m)+L1(n)*L2(m)/t;
                  m=t;
              end
                  flag=1;flag1=0;
                  break;%返回最外层的while进行循环
           else
               break;%跳出for循环，进行内层的while循环
           end
        end
    end
        if flag%找不到后继顶点 跳到第二个while，或找到增大流量的一条路
           R=union(R,u);
           break;
       end
   end%第三个while结束
end%第二个while结束
end%第一个while结束