图论算法-最大流算法和最大匹配算法.doc

最大流算法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;while maxf(n)0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (isempty(list)&(maxf(n)=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(n)0 v2=n; v1=pred(v2); while v2=1 if v10 f(v1,v2)=f(v1,v2)+maxf(n); else v1=abs(v1); f(v2,v1)=f(v2,v1)-maxf(n); end v2=v1; v1=pred(v2); end end endffunction f,wf,No=MaxFlowMinCut_Me(n,C)% 利用Ford-Fulkerson 标号法求最大流算法的MATLAB 程序代码% f %显示最大流% wf %显示最大流量% No %显示标号, 由此可得最小割% n 节点个数% C %弧容量 最大流算法 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号while(1)No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程for(i=1:n)if(No(i) %选择一个已标号的点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) %对于未给标号的点vj, 当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)|pd)break;end;end %若收点vt 得到标号或者无法标号, 终止标号过程if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt 表示调整量while(1)if(No(t)0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整elseif(No(t)0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧调整if(No(t)=1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %当t 的标号为vs 时, 终止调整过程t=No(t);end;end; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end endn=6; C=0 3 0 3 0 00 0 1 20 0 00 0 0 0 0 30 0 0 0 10 0 0 4 2 0 0 130 0 0 0 0 0; f,wf,No=MaxFlowMinCut_Me(n,C)最大匹配算法A=1 1 0 1 00 1 1 1 01 0 1 0 10 1 1 0 00 0 0 1 1;A=1 0 0 1 00 1 1 1 00 0 0 1 11 1 0 0 10 0 1 0 1;A=1 1 0 1 00 1 1 1 01 0 1 0 10 1 1 0 00 0 0 1 1;A=1 0 0 1 00 1 1 1 00 0 0 1 11 1 0 0 10 0 1 0 1;A=1 0 0 1 00 1 0 1 00 1 0 0 11 1 1 0 00 0 1 1 1;m=5;n=5;M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j)M(i,j)=1;break;end;end %求初始匹配Mif(M(i,j)break;end;end %获得仅含一条边的初始匹配Mwhile(1)for(i=1:m)x(i)=0;end %将记录X中点的标号和标记*for(i=1:n)y(i)=0;end %将记录Y中点的标号和标记*for(i=1:m)pd=1; %寻找X中M的所有非饱和点for(j=1:n)if(M(i,j)pd=0;end;endif(pd)x(i)=-n-1;end;end %将X中M的所有非饱和点都给以标号0 和标记*, 程序中用n+1 表示0 标号, 标号为负数时表示标记*pd=0;while(1)xi=0;for(i=1:m)if(x(i)1)k=k-1;for(j=1:k)pdd=1;for(i=1:m)if(M(i,yy(j)x(i)=-yy(j);pdd=0;break;end;end %将yj 在M中与之邻接的点xk (即xkyjM), 给以标号j 和标记*if(pdd)break;end;endif(pdd)k=1;j=yy(j); %yj 不是M的饱和点while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j); %任取M的一个非饱和点yj, 逆向返回if(j=n+1)break;end %找到X中标号为0 的点时结束, 获得M-增广路Pk=k+1;endfor(i=1:k)if(M(P(i,1),P(i,2)M(P(i,1),P(i,2)=0; %将匹配M 在增广路P 中出现的边去掉else M(P(i,1),P(i,2)=1;end;end %将增广路P 中没有在匹配M中出现的边加入到匹配M中break;end;end;endif(pd)break;end;end %假如X中所有有标号的点都已去掉了标记*, 算法终止M %显示最大匹配M, 程序结束利用可行点标记求最佳匹配算法的 MATLAB 程序代码如下：n=5;A=3 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3;for(i=1:n)L(i,1)=0;L(i,2)=0;endfor(i=1:n)for(j=1:n)if(L(i,1)L(S(i),1)+L(j,2)-A(S(i),j)al=L(S(i),1)+L(j,2)-A(S(i),j);end;end;endfor(i=1:jss)L(S(i),1)=L(S(i),1)-al;end %调整可行点标记for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end %调整可行点标记for(i=1:n)for(j=1:n) %生成子图GLif(L(i,1)+L(j,2)=A(i,j)Gl(i,j)=1;else Gl(i,j)=0;endM(i,j)=0;k=0;end;endii=0;jj=0;for(i=1:n)for(j=1:n)if(Gl(i,j)ii=i;jj=j;break;end;endif(ii)break;end;end %获得仅含Gl 的一条边的初始匹配MM(ii,jj)=1;breakelse %NL(S)Tfor(j=1:jsn)pd=1; %取yNL(S)Tfor(k=1:jst)if(T(k)=NlS(j)pd=0;break;end;endif(pd)jj=j;break;end;endpd=0; %判断y 是否为M的饱和点for(i=1:n)if(M(i,NlS(jj)pd=1;ii=i;break;end;endif(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj); %S=Sx, T=Tyelse %获得Gl 的一条M-增广路, 调整匹配Mfor(k=1:jst