Fold-Fulkerson求最小割

function [M,maxflow]=FoldFulkerson(A) %输入：A为原图的邻接矩阵 %输出：M为最大流值，maxflow为此时的可行流 %maxflow从零流开始慢慢增广，A是残量网络 m=size(A,1);%压缩表中最大值就是邻接矩阵的宽与高 maxflow=zeros(m,m); while 1 %下面用广度优先搜索找增广路径 flag=[];%相当于closed表，已访问过的节点不再访问 flag=[flag 1];%访问一个增加一个在该标志中 head=1;%判断是不是tail的后继节点 tail=1;%第一个节点，判断是谁的前趋 queue=[];%队列，相当于open表，将要访问的节点 queue(head)=1; head=head+1; pa=zeros(1,m); %每个节点的前趋 pa(1)=1; %源节点前趋是自己 while tail~=head %广度优先搜索，判断是否每一个节点的前趋都已经找到 i=queue(tail); for j=1:m if A(i,j)>0 && isempty(find(flag==j,1))%flag里面没有等于j的值 queue(head)=j; head=head+1; flag=[flag j]; pa(j)=i; end end tail=tail+1; end if pa(m)==0 %如果搜索不到汇节点，退出循环 break; end path=[]; i=m; %从汇节点开始 k=0; %路径包含的边的个数 while i~=1 %使用前趋构造从源节点到汇节点的路径 path=[path;pa(i) i A(pa(i),i)]; %存入路径，从得到的前趋节点数组中能得到找到的增广路经 i=pa(i); %使用前趋表反向搜寻，借鉴Dijsktra中的松弛方法 k=k+1; end Mi=min(path(:,3)); %寻找（残量网络中）增广路径中最小的那条边 for i=1:k A(path(i,1),path(i,2))=A(path(i,1),path(i,2))-Mi;%更新残量网络 maxflow(path(i,1),path(i,2))=maxflow(path(i,1),path(i,2))+Mi; %给零流增广，寻找可行最大流 end %使用新的图A进入下一循环，从新开始找增广路径 end M=sum(maxflow(1,:));