clear all
%圖論網(wǎng)絡(luò)流最大流 Ford-Fulkerson標(biāo)號算法
n=6;%六個頂點
%C為容量的鄰接的矩陣
C=[0,16,20,0,0,0;
   0,0,0,10,10,0;
   0,0,0,6,6,0;
   0,0,0,0,0,10;
   0,0,0,0,0,16;
   0,0,0,0,0,0];
f=zeros(n,n);%F為流,初始流為0流

while 1%大循環(huán)

%標(biāo)號過程
%標(biāo)號初始化
No=zeros(1,6);d=zeros(1,6);%No記錄該點標(biāo)號的獲得點 d記錄調(diào)整量
No(1)=n+1;d(1)=inf;%給發(fā)點Vs標(biāo)號
while 1%標(biāo)號循環(huán)
pd=0;
for i=1:n
for j=1:n
if No(i)~=0%選擇一個已標(biāo)號的點x
if No(j)==0%對于它的未標(biāo)號鄰接點y
if C(i,j)>0%當(dāng)(x,y)是一條邊時
if f(i,j)<C(i,j)%判斷增廣鏈條件
No(j)=i;        %標(biāo)號 
d(j)=min([C(i,j)-f(i,j),d(i)]);
pd=1;
end
end
if C(j,i)>0%當(dāng)(y,x)是一條邊時
if f(j,i)>0%判斷增廣鏈條件
No(j)=-i;   %標(biāo)號
d(j)=min([f(j,i),d(i)]);
pd=1;
end
end
end
end
end
end

if No(n)==1%當(dāng)Vt表上號時跳出標(biāo)號循環(huán)
break;
end
if pd==0; %當(dāng)無法標(biāo)號時跳出標(biāo)號循環(huán)
break;
end
end

if No(n)==0%當(dāng)Vt無法表上號時跳出大循環(huán)此時已是最大流
break;
end

%調(diào)整過程
t=n;%t為正在調(diào)整的點
for i=1:n %調(diào)整循環(huán)
if No(t)>0%正向流入的增加
f(No(t),t)=f(No(t),t)+d(n);
end
if No(t)<0%反向流出的減小 
f(t,abs(No(t)))=f(t,abs(No(t)))-d(n);
end

if abs(No(t))==1%如果下一個點為發(fā)點跳出調(diào)整循環(huán)
break;
else
t=abs(No(t));%繼續(xù)調(diào)整上游點   
end
end

end
f%顯示最大流
wf=0;
for i=1:n
wf=f(1,i)+wf;
end
wf%顯示最大流流量
No%顯示最小割