精心整理图论算法matlab实现求最小费用最大流算法的 MATLAB 程序代码如下：n=5;C=[0 15 16 0 00 0 0 13 14forwhileforfor(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;endfor(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ;end;endif(pd)break;end;end %求最短路的Ford 算法结束if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有whileifelseifififpd=0;值t=n;ifelseifif(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程t=s(t);endif(pd)break;end%如果最大流量达到预定的流量值wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用f %显示最小费用最大流图 6-22wf %显示最小费用最大流量zwf %显示最小费用, 程序结束__Kruskal 避圈法：k=1; %forifkk=1;for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end %排除相同的正数k=k+kk;end;end;endk=k-1 %显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k) %将x 中不同的正数从小到大排序if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;endT(n,n)=0; %将矩阵T 中所有的元素赋值为0q=0; %记录加入到树T 中的边数for(s=1:k)if(q==n)break;end %获得最小生成树T, 算法终止for(i=1:n-1)for(j=i+1:n)if (A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T 中TT=T;whileforforifif(pd)pd=0;forifelseT %用2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞D=A; %赋初值for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k, j); %k %D %R %pd=0;ifif(pd)end %0 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 0 0 0 0 0 0 0]; %弧容量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 记录标号图 6-19while(1)whileforfor弧时ifelseifififif(pd)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 %计算最大流量f %显示最大流wf %显示最大流量No %显示标号, 由此可得最小割, 程序结束ifforendelseifforW(a(1),a(2))=1;W(a(2),a(1))=1;endelsefprint('Please imput the right value of f');endW;程序二：可达矩阵算法function P=dgraf(A)精心整理n=size(A,1);P=A;for i=2:nP=P+A^i;endP(P~=0)=1;P;程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f==0forendelseifforendelsefprint('Please imput the right value of f');endW;第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function [l,z]=Dijkstra(W)l(i)=W(1,i);z(i)=0;endi=1;while i<=nfor j =1 :nif l(i)>l(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;endendendendendend程序三：n2short.m 计算指定两点间的最短距离function [P u]=n2short(W,k1,k2)n=length(W);U=W;m=1;for j=1:nif U(i,j)>U(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);k=1;kk=k2;whileforendendk=1;forendP;)function[Pm D]=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1:n[P d]=n2short(W,k,i);Pm{i}=P;D(i)=d;end程序五：pass2short.m(计算经过某两点的最短距离)精心整理function [P d]=pass2short(W,k1,k2,t1,t2) [p1 d1]=n2short(W,k1,t1);[p2 d2]=n2short(W,t1,t2);[p3 d3]=n2short(W,t2,k2);dt1=d1+d2+d3;[p4 d4]=n2short(W,k1,t2);[p5 d5]=n2short(W,t2,t1);[p6 d6]=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1<dt2d=dt1;elseendP;d;ifforendendelseb=d;endn=max(max(b(1:2,:)));m=size(b,2);[B,i]=sortrows(b',3);B=B';c=0;T=[];精心整理k=1;t=1:n;for i=1:mif t(B(1,i))~=t(B(2,i))T(1:2,k)=B(1:2,i);c=c+B(3,i);k=k+1;tmin=min(t(B(1,i)),t(B(2,i))); tmax=max(t(B(1,i)),t(B(2,i)));for j=1:nif t(j)==tmaxt(j)=tmin;endc;k=1:l;e=1;whileformin=a(i,j);b=a(i,j); s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;精心整理e=e+1;endT=[source;destination];for g=1:e-1c(g)=a(T(1,g),T(2,g));endc;另外两种程序最小生成树程序1（prim 算法构造最小生成树）endresult最小生成树程序2（Kruskal 算法构造最小生成树）clc;clear;a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;精心整理a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;[i,j,b]=find(a);data=[i';j';b'];index=data(1:2,:);loop=max(size(a))-1;endendresult第四讲：Euler图和Hamilton图程序一：Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m, edf.m, flecvexf.mfunction [T c]=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0b(b==inf)=0;b(b~=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:nifendendif m~=0endif m==0forfor g=1:edsc=c+d(T(1,g),T(2,g));endflagg=0;break;endendendendfunction[flag ed]=edf(matr,eds,vexs,ed,tem)[dvex f]=flecvexf(matr,i,vexs,eds,ed,tem);if f==1flag=0;break;endif dvex~=0ed(:,i)=[vexs(1,i) dvex];vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i))=0;endendf=0;dvex=0;ded=[];ifelseforendif kkk==length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=[tem;edd];for l1=1:kkklt=0;ddd=1;for l2=1:edsif edd1(1:2,l1)==ed(1:2,l2)lt=lt+1;endend精心整理if lt==0ded(ddd)=edd(l1);ddd=ddd+1;endendendif temp<=length(dvex1)dvex=dvex1(temp);elseif temp>length(dvex1) & temp<=length(ded)dvex=ded(temp);elseendend路）%d%Cendendendd2=0;for i=1:nif i<nd2=d2+d(i,i+1);elsed2=d2+d(n,1);endendtext(10,30,num2str(d2));n=size(d,2);C=[linspace(1,n,n) 1];for nnn=1:20C1=C;if n>3for m=4:n+1for i=1:(m-3)for j=(i+2):(m-1)if (d(C(i),C(j))+d(C(i+1),C(j+1))<d(C(i),C(i+1))+d(C(j),C(j+1))) C1(1:i)=C(1:i);for k=(i+1):jd1;endfor i=1:nstr1='V';str2=num2str(i);dot=[str1,str2];text(v(i,1)-1,v(i,2)-2,dot); %给点命名endv2=[v;v(1,1),v(1,2)];plot(v(C(:),1),v(C(:),2),'r');text(10,30,num2str(d1));第五讲：匹配问题及算法程序一：较大基础匹配算法function J=matgraf(W)n=size(W,1);J=zeros(n,n);while sum(sum(W))~=0a=find(W~=0);t1=mod(a(1),n);if t1==0t1=n;endifendendJ;ifendb=a;ifendfor i =1:m(1)b(i,:)=b(i,:)-min(b(i,:));endfor j=1:m(2)b(:,j)=b(:,j)-min(b(:,j));endd=(b==0);[e,total]=fc02(d);while total~=m(1)b=fc03(b,e);精心整理d=(b==0);[e,total]=fc02(d);endinx=sub2ind(size(a),e(:,1),e(:,2)); e=[e,a(inx)];s=sum(a(inx));function [e,total]=fc02(d)total=0;m=size(d);e=zeros(m(1),2);t=sum(sum(d)');nump=sum(d');whileendwhiletp=sum(p+q);inp=find(p==1);n=size(inp);for i=1:n(1)inq=find(b(inp(i),:)==0); q(inq)=1;endinp=find(q==1);n=size(inp);for i=1:n(1)精心整理if all(e(:,2)-inp(i))==0inq=find((e(:,2)-inp(i))==0);p(e(inq))=1;endendtq=sum(p+q);t=tq-tp;endinp=find(p==1);inq=find(q==0);cmin=min(min(b(inp,inq))');for%求初始匹配Mif(M(i,j))break;end;end %获得仅含一条边的初始匹配M while(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 表示0for取Xif标记for;e nd %if(k>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 (即xkyj∈M), 给以标号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 M-增广路forM去掉Mif*,M %程序3 Kuhn-Munkres算法（即赋权完备二元图的最佳匹配程序）function kk=kexingdian(A)%求赋权完备二元图最佳匹配A=[4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1]; %A为邻接矩阵n=length(A);for(i=1:n)L(i,1)=0;L(i,2)=0;endfor(i=1:n)for(j=1:n)if(L(i,1)<A(i,j))L(i,1)=A(i,j);end; %初始可行点标记L M(i,j)=0;end;endfor(i=1:n)for(j=1:n) %生成子图Glif(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;jsn=0;for(i=1:jss)for(j=1:n)if(Gl(S(i),j))jsn=jsn+1;NlS(jsn)=j; %NL(S)={v|u ∈S,uv∈EL}for(k=1:jsn-1)if(NlS(k)==j)jsn=jsn-1;end;end;end;end;endif(jsn==jst)pd=1; %判断NL(S)=T?for(j=1:jsn)if(NlS(j)~=T(j))pd=0;break;end;end;end if(jsn==jst&pd)al=Inf; %如果NL(S)=T, 计算al, Inf为∞ for(i=1:jss)for(j=1:n)pd=1;for(k=1:jst)if(T(k)==j)pd=0;break;end;endfor(j=1:jsn)pd=1; %取y∈NL(S)\Tfor(k=1:jst)if(T(k)==NlS(j))pd=0;break;end;end if(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=S∪{x}, T=T∪{y}else %获得Gl 的一条M-增广路, 调整匹配 Mfor(k=1:jst)M(S(k),T(k))=1;M(S(k+1),T(k))=0;endif(jst==0)k=0;endM %%C%f1%f%wfifelsef=f1;endNo=zeros(1,n);d=zeros(1,n);while (1)No(1)=n+1;d(1)=Inf;while (1)pd=1;for (i=1:n)精心整理if (No(i))for (j=1:n)if (No(j)==0 & f(i,j)<C(i,j))No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if (d(j)>d(i))d(j)=d(i);endelseif (No(j)==0 & f(j,i)>0)No(j)=-i;d(j)=f(j,i);pd=0;if (d(j)>d(i))d(j)=d(i);endifendendt=No(t);endendwf=0;for (j=1:n)wf=wf+f(1,j);endf;wf;精心整理程序二：Busacker-Gowan算法(求最大流最小费用)%C=[0 15 16 0 0;0 0 0 13 14;0 11 0 17 0;0 0 0 0 8;0 0 0 0 0]%b=[0 4 1 0 0;0 0 0 6 1;0 2 0 3 0;0 0 0 0 2;0 0 0 0 0]%function [f wf zwf]=BGf(C,b)%C表示弧容量矩阵%b表示弧上单位流量的费用%f表示最大流最小费用矩阵%wf最大流量%zwf表示最小费用n=size(C,2);whileforendforendforendforfor (i=2:n)for (j=1:n)if (p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;endendendif (pd)break;end精心整理endif (p(n)==inf)break;enddvt=inf;t=n;while (1)if (a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t);elseif (a(s(t),t)<0)dvtt=f(t,s(t));endendifendendif (pd)break;endwf=0;for (j=1:n)wf=wf+f(1,j);endendzwf=0;for (i=1:n)精心整理for (j=1:n)zwf=zwf+b(i,j)*f(i,j);endend。