資源描述：
《圖論算法 最大流算法和最大匹配算法.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、最大流算法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;whilemaxf(n)>0maxf=zeros(1,n);pred=zeros(1,n);list=1;record=list;maxf(1)=M;while(~isempty(list))&(maxf(n)==0)flag=list
2、(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(
3、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);endifmaxf(n)>0v2=n;v1=pred(v2);whilev2~=1ifv1>
4、0f(v1,v2)=f(v1,v2)+maxf(n);elsev1=abs(v1);f(v2,v1)=f(v2,v1)-maxf(n);endv2=v1;v1=pred(v2);endendendffunction[f,wf,No]=MaxFlowMinCut_Me(n,C)%利用Ford--Fulkerson標(biāo)號法求最大流算法的MATLAB程序代碼%f%顯示最大流%wf%顯示最大流量%No%顯示標(biāo)號,由此可得最小割%n節(jié)點(diǎn)個數(shù)%C%弧容量最大流算法for(i=1:n)for(j=1:n)f(i,j)=0;end;end%取初始可行流
5、f為零流for(i=1:n)No(i)=0;d(i)=0;end%No,d記錄標(biāo)號while(1)No(1)=n+1;d(1)=Inf;%給發(fā)點(diǎn)vs標(biāo)號while(1)pd=1;%標(biāo)號過程for(i=1:n)if(No(i))%選擇一個已標(biāo)號的點(diǎn)vifor(j=1:n)if(No(j)==0&f(i,j)d(i))d(j)=d(i);endelseif(No(j)==0&f(j,i)>0)%對于未
6、給標(biāo)號的點(diǎn)vj,當(dāng)vjvi為非零流弧時No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)>d(i))d(j)=d(i);end;end;end;end;endif(No(n)
7、pd)break;end;end%若收點(diǎn)vt得到標(biāo)號或者無法標(biāo)號,終止標(biāo)號過程if(pd)break;end%vt未得到標(biāo)號,f已是最大流,算法終止dvt=d(n);t=n;%進(jìn)入調(diào)整過程,dvt表示調(diào)整量while(1)if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt;%前向弧調(diào)整elseif(No(t)<0)f(No(
8、t),t)=f(No(t),t)-dvt;end%后向弧調(diào)整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0;end;break;end%當(dāng)t的標(biāo)號為vs時,終止調(diào)整過程t=No(t);end;end;%繼續(xù)調(diào)整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);endendn=6;C=[030300001200000000300001000420013000000];[f,wf,No]=MaxFlowMinCut_Me(n,C)最大匹配算法A=[1101001110101010110000
9、011];A=[1001001110000111100100101];A=[1101001110101010110000011];A=[1001001110000111100100101];A=[100100101001
