matlab图论程序算法大全.pdf

精心整理图论算法matlab实现求最小费用最大流算法的MATLAB程序代码如下：n=5;C=[0151600000131401101700000800000];%弧容量b=[0410000061020300000200000];%弧上单位流量的费用wf=0;wf0=Inf;%wf表示最大流量,wf0表示预定的流量值for(i=1:n)for(j=1:n)f(i,j)=0;end;end%取初始可行流f为零流while(1)for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图for(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的最短路2019年9月精心整理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的最短路,算法终止.注意在求最小费用最大流时构造有向赋权图中不会含负权回路,所以不会出现k=ndvt=Inf;t=n;%进入调整过程,dvt表示调整量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));end%后向弧调整量if(dvt>dvtt)dvt=dvtt;endif(s(t)==1)break;end%当t的标号为vs时,终止计算调整量t=s(t);end%继续调整前一段弧上的流fpd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值t=n;while(1)%调整过程if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt;%前向弧调整elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end%后向弧调整if(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%计算最小费用2019年9月精心整理f%显示最小费用最大流图6-22wf%显示最小费用最大流量zwf%显示最小费用,程序结束__Kruskal避圈法：Kruskal避圈法的MATLAB程序代码如下：n=8;A=[0281000020601000860751201070009001500308001030460029040300008630];k=1;%记录A中不同正数的个数for(i=1:n-1)for(j=i+1:n)%此循环是查找A中所有不同的正数if(A(i,j)>0)x(k)=A(i,j);%数组x记录A中不同的正数kk=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;end2019年9月精心整理T(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;%临时记录Twhile(1)pd=1;%砍掉TT中所有的树枝for(y=1:n)kk=0;for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end%寻找TT中的树枝if(kk==1)T