matlab图论程序算法大全推荐文档

1、精心整理图论算法matlab实现求最小费用最大流算法的MATLAB程序代码如下：n=5;C=0 15 16 0 00 0 0 13 14011 017 00 0 0 0 80 0 0 0 0;%弧容量b=0 4 1 0 0- 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)=lnf;s(i)二i;end %用 Ford 算法求最短路，赋初值for (k=1:n)

2、pd=1;%求有向赋权图中vs到vt的最短路2019年9月精心整理endfor (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=O;end; endif (pd) break; end;end %求最短路的Ford算法结束if (p(n)=lnf) break; end %不存在vs到vt的最短路，算法终止.注意在求最小费用最大流时构造有向赋权图中不会含负权回路，所以不会出现k=ndvt=Inf;t=n;%进入调整过程，dvt表示调整量while (1) %计算调整量if (a(s(t),t)0)dvtt=C(

3、s(t),t)-f(s(t),t);%前向弧调整量elseif (a(s(t),t)dvtt)dvt=dvtt; endi I x 1iif (s(t)=1) break; end %当t的标号为vs时，终止计算调整量j-J _t=s(t); end %继续调整前一段弧上的流fpd=0; if (wf+dvt=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值,-jI ft=n; while (1) %调整过程if (a(s(t),t)O)f(s(t),t)=f(s(t),t)+dvt;%前向弧调整elseif (a(s(t),t)0)x(k)=A(i,j);%

4、数组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中不同的正数从小到大排序end; end; endif (x(j)0)kk=kk+1;zz=z; end; end 扇找 TT 中的树枝 if (kk=1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end; end %砍掉TT 中的树枝if (pd) break; end;end %

5、已砍掉了 TT中所有的树枝1 i X 1pd=0; %判断TT中是否有圈J-J _for (y=1:n-1) for (z=y+1:n) if (TT(y,z)0)pd=1; break; end; end; end if (pd)T(i,j)=0;T(j,i)=0;%假如 TT 中有圈ielse q=q+1;end; end; end; end; end,-j I fT %显示近似最小生成树T,程序结束用Warshall-Floyd算法求任意两点间的最短路n=8;A=0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf

6、1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 62019年9月精心整理Inf 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);%更新 dijR(i,j)=k; end; end;

7、 end %更新 rijk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径-? I y .： .*pd=0; for i=1:n %含有负权时$ . I X 1 t Zyfj ；. if (D(i,i)0)pd=1;break; end; end %存在一条含有顶点 vi 的负回路j- 丿if (pd) break; end %存在一条负回路，终止程序end %程序结束利用Ford-Fulkerson标号法求最大流算法的MATLAB,-jI/芦# /程序代码如下：n二 8;C=0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0

8、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 52019年9月精心整理0 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-19 while (1)No(1)=n+1;d(1)=lnf;%给发点 vs 标号while (1)pd=1;%标号过程for (i=1:n) if (No(i)%选择一个已标号的点vifor (j=1:n) if (No(j)

9、=0&f(i,j)d(i)d(j)=d(i);endp y xelseif (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; end,-jI fif (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(

10、No(t),t)=f(No(t),t)+dvt;elseif (No(t)0)f(No(t),t)=f(No(t),t)-dvt;if (No(t)=1) for (i=1:n)No(i)=0;d(i)=0;终止调整过程2019年9月%前向弧调整end %后向弧调整end; break; end %当 t 的标号为 vs 时精心整理t二No(t); end;end; %继续调整前一段弧上的流fwf=O; for (j=1:n)wf=wf+f(1,j); end %+算最大流量f %显示最大流wf %显示最大流量No混示标号，由此可得最小割，程序结束图论程序大全程序一：关联矩阵和邻接矩阵互换算法

11、fun cti on W=i ncan dadf(F,f)if f=0m=sum(sum(F)/2;n=size(F,1);W=zeros( n, m);k=1;for i=1: nfor j=i:nif F(i,j)=0W(i,k)=1;W(j,k)=1;k=k+1;endendendelseif f=1m=size(F,2);n=size(F,1);W=zeros( n,n);for i=1:ma=fi nd(F(:,i)=0);W(a(1),a (2)=1;W(a(2) ,a(1)=1;endelsefprint( Please imput the right value of f);e

12、ndW;程序二：可达矩阵算法fun cti on P=dgraf(A)精心整理n=size(A,1);P=A;for i=2:nP=P+AAi;endP(P=0)=1；P；程序三：有向图关联矩阵和邻接矩阵互换算法fun cti on W=mattra nsf(F,f)if f=0m=sum(sum(F);n=size(F,1);W=zeros( n, m);k=1;for i=1: nfor j=i:n if F(i,j)=OW(i,k)=1;W(j,k)=-1;k=k+1;endIendendelseif f=1m=size(F,2);n=size(F,1);W=zeros( n,n);fo

13、r i=1:ma=fi nd(F(:,i)=0);if F(a(1),i)=1W(a(1),a (2)=1;elseW(a(2) ,a(1)=1;endendelsefprint( Please imput the right value of f);endW;第二讲：最短路问题程序一：Dijkstra算法(计算两点间的最短路)fun ctio n l,z=Dijkstra(W)2019年9月精心整理n = size (W,1);for i = 1 :nl(i)=W(1,i);z(i)=0；endi=1;while il(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1；i

14、f jii=j-1;endendendi=i+1;end程序二：floyd算法(计算任意两点间的最短距离) fun cti on d,r=floyd(a)n=size(a,1);d=a;for i=1: nfor j=1: nr(i,j)=j;endend/二7 I r;for k=1: nI_ :for i=1:nfor j=1: nif d(i,k)+d(k,j)vd(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k);endendendend程序三：n 2short.m计算指定两点间的最短距离fun ctio n P u=n2short(W,k1,k2)n=

15、le ngth(W);U=W;m=1;精心整理while mU(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(1, n);k=1;P1(k)=k2;V=o nes(1, n)* inf;kk=k2;while kk=k1for i=1: nV(1,i)=U(k1,kk)-W(i,kk);if V(1,i)=U(k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=fi nd(P1=0);for j=length(wrow):-1:1P(k)=P1(wrow(j);k=

16、k+1;endP;程序四、n1short.m(计算某点到其它所有点的最短距离)function Pm D=n1short(W,k)n=size(W,1);D=zeros(1, n);for i=1: nP d=n2short(W,k,i);Pmi=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=n2s

17、hort(W,k1,t2);p5 d5=n2short(W,t2,t1);p6 d6=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1dt2d=dt1;P=p1 p2(2:le ngth(p2) p3(2:le ngth(p3);elsed=dt1;p=p4 p5(2:le ngth(p5) p6(2:le ngth(p6);endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法i 1 I X 1tfun cti on T c=krusf(d,flag)if nargin=1n=size(d,2);m=sum(sum(d=0)/2;b=zeros(3,m

18、);k=1;for i=1: nfor j=(i+1):nif d(i,j)=0b(1,k)=i;b(2,k)=j;b(3,k)=d(i,j);k=k+1;endendendelseb=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;tmi n=mi n( t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i);for j

19、=1: nif t(j)=tmax t(j)=tmi n;endendendif k=nbreak;endendT;c;程序二：最小生成树的Prim算法I 1 ,fun cti on T c=Primf(a)l=le ngth(a);a(a=0)=i nf;k=1:l;listV(k)=0;listV(1)=1;e=1;while (ea(i,j)min=a(i,j);b=a(i,j); s=i;d=j;endendendendlistV(d)=1;dista nce(e)=b;source(e)=s;dest in ati on( e)=d;精心整理e=e+1;endT=source;des

20、ti nati on;for g=1:e-1c(g)=a(T(1,g),T(2,g);endc;另外两种程序最小生成树程序1 (prim算法构造最小生成树)a=inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf45;inf 65 52 inf 50 30 42;i nf 40 inf 50 inf 70 inf;inf inf inf 30 70 infinf;.inf inf 45 42 inf inf inf;result=;p=1;tb=2:le ngth(a);while len gth(re

21、sult)=le ngth(a)-1temp=a(p,tb);temp=temp(:);d=mi n(temp);jb,kb=fi nd(a(p,tb)=d);2-vX ： Zj=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(fi nd(tb=k)=;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

22、,6)=70;i,j,b=find (a);data二i;j;b;i ndex=data(1:2,:);loop二max(size(a)-1;result=;while len gth(result)le ngth(dvexl) & temp=le ngth(ded)dvex=ded(temp);elsef=1;endend程序二：Hamilton改良圈算法(找出比较好的Hamilton路)function C d1= hamiltonglf(v)%表示权值矩阵%表示算法最终找到的Hamilton圈。 %v = 51 67;37 84;41 94;2 99;18 54;4 50;24 42;2

23、5 38;13 40;7 64;22 60;25 62;18 40;41 26;n=size(v,1);subplot(1,2,1)hold on;plot (v(:,1),v(:,2),*); %描点for i=1: nstr1=V;str2=nu m2str(i);dot=str1,str2;text(v(i,1)-1,v(i,2)-2,dot); %给点命名endplot (v(:,1),v(:,2);% 连线plot(v( n,1),v(1,1),v( n,2),v(1,2);for i =1: nfor j=1: nd(i,j)=sqrt(v(i,1)-v(j,1)A2+(v(i,2

24、)-v(j,2)A2);endendd2=0;for i=1: nif i3for 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):jC1(k)=C(j+i+1-k);endC1(j+1):m)=C(j+1):m);endendendendelseif n=3if nfloor(a(1)/n)t2=floor(a(1)/n)+1;elset2=floor(a(1)/n);endJ(t1,t2)=1,

25、J(t2,t1)=1;W(t1,:)=0;W(t2,:)=0;W(:,t1)=0;W(:,t2)=0;endJ;,包括三个文件程序二：匈牙利算法(完美匹配算法fc01,fc02,fc03)fun cti on e,s=fc01(a,flag)if nargin=1flag=0;endb=a;if flag=0cmax=max(max(b);b=cmax-b;endm=size(b);for i =1:m(1)b(i,:)=b(i,:)-mi n( b(i,:);endfor j=1:m(2)b(:,j)=b(:,j)-mi n( b(:,j);endd=(b=0);e,total=fc02(d

26、);while total=m(1)b=fc03(b,e);精心整理d=(b=O);e,total=fc02(d);endin x=sub2 in d(size(a),e(:,1),e(:,2); e=e,a(i nx);s=sum(a(i nx);fun ctio n e,total=fc02(d) total=0;m=size(d); e=zeros(m(1),2); t=sum(sum(d);nu mp二sum(d);while t=0s,i np=sort (nu mp);inq=fin d(s);ep=i np(i nq(1);in p=fi nd(d(ep,:);num q=sum

27、(d(:,i np);s,i nq=sort (num q);eq=i np(i nq(1);total=total+1; e(total,:)=ep,eq; in p=fi nd(d(:,eq);nu mp(i np)=nu mp(i np)-1;nu mp(ep)=0;t=t-sum(d(ep,:)-sum(d(:,eq)+1; d(ep,:)=0*d(ep,:);d(:,eq)=0*d(:,eq);endfun ctio n b=fc03(b,e) m=size(b);t=1;p=o nes(m(1),1); q=zeros(m(1),1);in p=fi nd(e(:,1)=0);p(

28、e(i np,1)=0;while t=0tp=sum(p+q);in p=fi nd(p=1);n=size(i np);for i=1: n(1) inq=fin d(b(i np(i),:)=0);q(i nq)=1;endin p=fi nd(q=1);n=size(i np);for i=1: n(1)精心整理if all(e(:,2)-inp(i)=Oin q=fi nd(e(:,2)-i np(i)=O);p(e(i nq )=1;endendtq=sum(p+q);t=tq-tp;endin p=fi nd(p=1);inq=fin d(q=O);cmi n=min(min (

29、b(i np,i nq);inq=fin d(q=1);b(i np,:)=b(i np,:)-cmi n;b(:,i nq)=b(:,i nq )+cmi n;运行以下程序求其最大解：输入矩阵a,然后输入t,m=fcO1(a)运行以下程序求其最小解：输入矩阵a，然后输入t,m=fcO1(a ，1)匈牙利算法的另一程序匈牙利算法的MATLAB程序代码如下： I X 1 tm=5; n=5;A=0 1 1 0 0_ .1二-1 1 0 1 10 1 1 0 00 1 1 0 0,-j I f0 0 0 1 1;M(m, n)=0;for (i=1:m) for (j=1:n) if (A(i,j

30、)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 %各记录丫中点的标号和标记*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标号,标号为负数时表示标

31、记*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 (即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 (j=n+1) break;

32、 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中出现的边- I -;去掉i I x 1 芦 %else M(P(i,1),P(i,2)=1; end; end %各增广路 P 中没有在匹配 M，-_中出现的边加入到匹配M中：i break; end; end; end,-jI fif (pd) break; end; end %假如X中所有有标号的点都已去掉了标记*,算法终止M %显示最大匹配M,程序结束程序3 Kuhn-Munkres算法(即赋权完

33、备二元图的最佳匹配 程序)fun ctio n kk=kexi ngdia n( A)% 求赋权完备二元图最佳匹配A=4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1; %A为邻接矩阵n=le ngth(A);2019年9月精心整理for(i=1: n)L(i,1)=0;L(i,2)=0;e nd初始可行点标记Lfor(i=1:n)for(j=1:n)if(L(i,1)L(S(i),1)+L(j,2)-A(S(i),j)a匸L(S(i),1)+L(j,2)-A(S(i),j);e nd;en d;e ndfor(i=1:jss)L(S(i),1)=L(S(i),1)-al;end

34、 %调整可行点标记for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end %调整可行点标记for(i=1:n)for(j=1:n) %生成子图 GL1T1Zif(L(i,1)+L(j,2)=A(i,j)Gl(i,j)=1;1 i X i if y #尹else Gl(i,j)=0;e ndM(i,j)=O;k=O;e nd;e ndii=0;jj=0;:? c i for(i=1: n) for(j=1: n)if(Gl(i,j)ii=i;jj=j;break;e nd;e nd,-jI# fif(ii)break;end;end %获得仅含Gl的一条边的初始匹配MM(i

35、i,jj)=1;breakelse %NL(S) 工 Tfor(j=1:js n)pd=1; %取 y NL(S)Tfor(k=1:jst)if(T(k)=NlS(j)pd=0;break;e nd;e nd if(pd)jj=j;break;e nd;e ndpd=0; % 判断y是否为M的饱和点for(i=1: n)if(M(i,NlS(jj)pd=1;ii=i;break;e nd;e nd2019年9月精心整理u X,if(pd)jss二jss+1;S(jss)二ii;jst二jst+1;T(jst)二NlS(jj); %S=ST=TU yelse % 获得Gl的一条M-增广路，调整匹配Mfor(k=1:jst)M(S(k),T(k)=1;M(S(k+1),T(k)=0;e nd if(jst=0)k=0;e ndM(S(k+1),NlS(jj)=1;break;e nd;e nd;e nd;e ndMaxZjpp=O;for(i=1: n)for(j=1: n)if(M(i,j)MaxZjpp=MaxZjpp+A(i,j);e nd;e nd;e ndM %显示最佳匹配MMaxZjpp %显示最佳匹