图论matlab程序大全

1、图论程序大全程序一：可达矩阵算法function P=dgraf(A)n=size(A,1);P=A;for i=2:nP=P+AendP(P-=0)=1;P；程序二：关联矩阵和邻接矩阵互换算法function W=incandadf(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=find(F(:

2、,i)=0);W(a(1),a(2)=1;W(a(2),a(1)=1;endelsefprint( 'Please imput the right value of f' );endW;程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f=0m=sum(sum(F);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

3、,n);for i=1:ma=find(F(:,i)=0);if F(a(1),i)=1W(a(1),a(2)=1;elseW(a(2),a(1)=1;endend；elsefprint( 'Please imput the right value of f' endW;第二讲：最短路问题程序一：Dijkstra算法(计算两点间的最短路)function l,z=Dijkstra(W)n = size (W,1);for i = 1 :nl(i)=W(1,i);z(i)=0;endi=1;while i<=nfor j =1 :nif l(i)>l(j)+W(j,i

4、)l(i)=l(j)+W(j,i);z(i)=j-1;if j<ii=j-1;endendendi=i+1;end程序二：floyd算法(计算任意两点间的最短距离)function d,r=floyd(a)n=size(a,1);d=a;for i=1:nfor j=1:nr(i,j)=j;endendr;for k=1:nfor i=1:nfor j=1:nif d(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k);endendendend程序三：n2short.m计算指定两点间的最短距离function P u=n2sho

5、rt(W,k1,k2)n=length(W);U=W;m=1;while m<=nfor i=1:nfor 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);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(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=find(P1=0);fo

6、r j=length(wrow):-1:1P(k)=P1(wrow(j);k=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

7、(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;P=p1 p2(2:length(p2) p3(2:length(p3);elsed=dt1;p=p4 p5(2:length(p5) p6(2:length(p6);endP；d；第三讲：最小生成树程序一：最小生成树的 Kruskal算法function T c=krusf(d,flag)if nargin=1n=size(d,2);m=sum(s

8、um(d=0)/2;b=zeros(3,m);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;tmin=min(t(B(1,i),t(B(2,i);tmax=max(t(B

9、(1,i),t(B(2,i);for j=1:nif t(j)=tmaxt(j)=tmin;endendendif k=nbreak ;endendT;c;程序二：最小生成树的 Prim算法function T c=Primf(a)l=length(a);a(a=0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while (e<l)min=inf;for i=1:lif listV(i)=1for j=1:lif listV(j)=0 & min>a(i,j) min=a(i,j);b=a(i,j); s=i;d=j;endendendendl

10、istV(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算法构造最小生成树)a=inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf 45;inf 65 52 inf 50 30 42;inf 40 inf 50 inf 70 inf;inf inf inf 30 70 inf in

11、f;.inf inf 45 42 inf inf inf;result=;p=1;tb=2:length(a);while length(result)=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=; endresult算法构造最小生成树最小生成树程序 2 ( Kruskal clc;clear;a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=4

12、0;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;result=;while length(result)<looptemp=min(data(3,:);flag=find(data(3,:)=temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);if index(1,flag)=index(2,flag) resu

13、lt=result,data(:,flag);endindex(find(index=v2)=v1;data(:,flag)=;index(:,flag)=;endresult第四讲：Euler图和Hamilton 图程序一：Fleury 算法(在一个 Euler图中找出Euler环游)注：包括三个文件；fleuf1.m, edf.m, flecvexf.mfunction T c=fleuf1(d)%注：必须保证是 Euler环游,否那么输出 T=0,c=0n=length(d);b=d;b(b=inf)=0;b(b=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zer

14、os(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:nif mod(a(i),2)=1m=m+1;endendif m=0fprintf( 'there is not exit Euler path.n' )T=0;c=0;endif m=0vet=1;flag=0;t1=find(matr(vet,:)=1);for ii=1:length(t1)ed(:,1)=vet,t1(ii);vexs(1,1)=vet;vexs(1,2)=t1(ii);matr(vexs(1,2),vexs(1,1)=0;flagg=1;tem=1;while

15、flaggflagg ed=edf(matr,eds,vexs,ed,tem);tem=tem+1;if ed(1,eds)=0 & ed(2,eds)=0T=ed;T(2,eds)=1;c=0;for g=1:edsc=c+d(T(1,g),T(2,g);endflagg=0;break ;endendendendfunction flag ed=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:edsdvex f=flecvexf(matr,i,vexs,eds,ed,tem);if f=1flag=0;break ;endif dvex=0ed(:,

16、i)=vexs(1,i) dvex;vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i)=0;elsebreak ;endendfunction dvex f=flecvexf(matr,i,vexs,eds,ed,temp)f=0;edd=find(matr(vexs(1,i),:)=1);dvex=0;dvex1=;ded=;if length(edd)=1dvex=edd;elsedd=1;dd1=0;kkk=0;for kk=1:length(edd)m1=find(vexs=edd(kk);if sum(m1)=0dvex1(dd)=edd(kk);

17、dd=dd+1;dd1=1;elsekkk=kkk+1;endendif 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;endendif lt=0ded(ddd)=edd(l1);ddd=ddd+1;endendendif temp<=length(dvex1)dvex=dvex1(temp);elseif temp>length(dvex1) & temp<=lengt

18、h(ded) dvex=ded(temp);elsef=1;endend程序二：Hamilton 改进圈算法(找出比拟好的Hamilton 路)function C d1= hamiltonglf(v)%d表示权值矩阵%C表示算法最终找到的 Hamilton圈.%v = 51 67;37 84;41 94;2 99;18 54;4 50;24 42;25 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:nstr

19、1='V'str2=num2str(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)-v(j,2)A2);endendd2=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,

20、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):jC1(k)=C(j+i+1-k);endC1(j+1):m)=C(j+1):m);endendendendelseif n<=3if n<=2fprint('It does not exist Hamilton circ

21、le.');elsefprint('Any cirlce is the right answer.');endendC=C1;d1=0;for i=1:nd1=d1+d(C(i),C(i+1);endd1;endsubplot(1,2,2);hold on;plot (v(:,1),v(:,2),'*');% 描点for 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(:),

22、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;endif a(1)/n>floor(a/n)t2=floor(a(1)/n)+1;elset2=floor(a/n);endJ(t1,t2)=1,J(t2,t1)=1;W(t1,:)=0;W(t2,:)=0;W(:,t1)=0;W(:,t2)=0;e

23、ndJ;程序二：匈牙利算法(完美匹配算法,包括三个文件fc01,fc02,fc03)function 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,:)-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

24、);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');while t=0s,inp=sort(nump);inq=find(s);ep=inp(inq(1);inp=find(d(ep,:);numq=sum(d(:,inp);s,inq=sort(numq);eq=inp(inq(1);total=total+1;e(total,:)=

25、ep,eq;inp=find(d(:,eq);nump(inp)=nump(inp)-1;nump(ep)=0;t=t-sum(d(ep,:)-sum(d(:,eq)+1;d(ep,:)=0*d(ep,:);d(:,eq)=0*d(:,eq);endfunction b=fc03(b,e)m=size(b);t=1;p=ones(m(1),1);q=zeros(m(1),1);inp=find(e(:,1)=0);p(e(inp,1)=0;while t=0tp=sum(p+q);inp=find(p=1);n=size(inp);for i=1:n(1)inq=find(b(inp(i),:

26、)=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)');inq=find(q=1);b(inp,:)=b(inp,:)-cmin;b(:,inq)=b(:,inq)+cmin;运行以下程序求其最大解：输入矩阵a,然后输入t,m=fc01(a)运行以下程序

27、求其最小解：输入矩阵a,然后输入t,m=fc01(a, 1)匈牙利算法的另一程序匈牙利算法的MATLAB程序代码如下：m=5;n=5;A=0 1 1 0 01 1 0 1 10 1 1 0 00 1 1 0 00 0 0 1 1;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; en

28、d %将记录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 %将*中M的所有非饱和点都给以标号0和标记*,程序中用n+1表示0标号,标号为负数时表示标记*pd=0;while (1)xi=0;for (i=1:m) if(x(i)<0)xi=i; break ;end ;end %假设X 中存在一个既有标号又有标记*的点,那么任取X中一个既有标号又有标记*的点xiif(xi=0)pd=1; break ;end %假设X中所有有标号的点

29、都已去掉了标记*,算法终止x(xi)=x(xi)*(-1);%去掉 xi 的标记*k=1;for (j=1:n) if (A(xi,j)&y(j)=0)y(j)=xi;yy(k)=j;k=k+1; end ;end %对与xi 令口接且 尚未给标号的yj都给以标号iif(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 %将的 在M 中与之 邻接的点xk (即xkyj CM),给以标号j和标记*if(pdd) break ;end ;endif(pdd)k=1

30、;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 ;e

31、nd ;end %假设X中所有有标号的点都已去掉了标记*,算法终止M %显小最大匹配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; %初始可行点标记 LM(i,j)=0;end;endfor(i=

32、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;end;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;for(i=1:n)S(i)=0;T(i)=0;NlS(i)=0;endwhile(1)for(i=1:n)k=1;for(j=1:n)if(M(i,j)k=0;break;end;endif(k)break;e

33、nd;endif(k=0)break;end %获得最彳i匹配M,算法终止S(1)=i;jss=1;jst=0;%S=xi, T=fwhile(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|uC S,uv C ELfor(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;endif(jsn

34、=jst&pd)al=Inf; % 如果 NL(S)=T,计算 al, Inf 为00for(i=1:jss)for(j=1:n)pd=1;for(k=1:jst)if(T(k)=j)pd=0;break;end;endif(pd&al>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

35、)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) wTfor(j=1:jsn)pd=1; %取 yC NL(S)Tfor(k=1:jst)if(T(k)=NlS(j)pd=0;break;end;end

36、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 Ux, T=T U yelse %获彳导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(S(k+1),NlS(jj)=1;break;end;end;end;endMaxZjpp=0;for(i=1

37、:n)for(j=1:n)if(M(i,j)MaxZjpp=MaxZjpp+A(i,j);end;end;endM %显示最正确匹配MMaxZjpp % 显示最正确匹配M的权,程序结束第六讲：最大流最小费用问题程序一：2F算法(Ford-Fulkerson算法),求最大流%C=0 5 4 3 0 0 0 0;0 0 0 0 5 3 0 0;0 0 0 0 0 3 2 0;0 0 0 0 0 0 2 0;%0 0 0 0 0 0 0 4;0 0 0 0 0 0 0 3;0 0 0 0 0 0 0 5;0 0 0 0 0 0 0 0 function f wf=fulkersonf(C,f1)%C

38、表示容量%f1表示当前流量,默认为0%f表示最大流士 i 6? X ? ' 6 & +%wf表示最大流的流量n=length(C);if nargin=1;f=zeros(n,n);elsef=f1;endNo=zeros(1,n);d=zeros(1,n);while (1)No6=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)

39、;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);endendendendendif (No(n)|pd)break ;endendif (pd)break ;enddvt=d(n);t=n;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;endif (No(t)=1)for (i=1:n)No(i)=0;d(i)=0;endb

40、reakendt=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);wf=0;wf0=i

41、nf;f=zeros(n,n);while (1)a=ones(n,n)*inf;for (i=1:n)a(i,i)=0;endfor (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);endendendfor (i=2:n)p(i)=inf;s(i)=i;endfor (k=1:n)pd=1;for (i=2:n)f

42、or (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 ;endendif (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);endif (dvt>dvtt) dvt=dvtt;endif (s(t)=1) break ;endt=s(t);endpd=0;if (wf+dvt>

43、=wf0)dvt=wf0-wf;pd=1;endt=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;endif (s(t)=1)break ;endt=s(t);endif (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);endendf；图论工具箱： :/ 根本图论函数库： :/ Dijkstra

44、 最短路径： :/ Kruskal 最小生成树： :/ Prims 算法： :/ A 星优化算法： :/ 图论算法及matlab实现用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 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 表示gD=A; %赋初值

45、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 ;end %更新 rijk %显示迭代步数D %显示每步迭代后的路长R%显示每步迭代后的路径pd=0; for i=1:n %含有负权时if(D(i,i)<0)pd=1; break ;end ;end %存在一条含有顶点 vi 的负回路 if (pd) break ;end %

46、存在一条负回路,终止程序 end %程序结束Kruskal避圈法：Kruskal避圈法的MATLAB 程序代码如下：n=8;A=0 2 8 1 0 0 0 02 0 6 0 1 0 0 08 6 0 7 5 1 2 01 0 7 0 0 0 9 00 1 5 0 0 3 0 80 0 1 0 3 0 4 60 0 2 9 0 4 0 30 0 0 0 8 6 3 0;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

47、 (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) %将*中不同的正数从小到大排序 if (x(j)<x(i)xx=x(j);x(j)=x(i);x(i)=xx; end ;end ;end T(n,n)=0; %将矩阵T中所有的元素赋值为0 q=0; %记录参加到树T中的边数for (s=1:k) if(q=n) break;end %获得最小生成树 T,算法终止for (i=1:n-1) fo

48、r (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)TT(y,zz)=0;TT(zz,y)=0;pd=0; end ;end %砍掉TT 中的树枝 if (pd) break ;end ;end %已砍掉了 TT中所有的树枝 pd=0; %判断TT中是否有圈for (y=

49、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 中有圈else q=q+1; end ;end ;end ;end ;endT %显示近似最小生成树T,程序结束利用Ford-Fulkerson标号法求最大流算法的MATLAB程序代码如下：n=8;C=0 5 4 3 0 0 0 00 0 0 0 5 3 0 0 0 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 4 0 0 0 0 0 0 0 30 0 0 0 0 0

50、 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)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)<C(i,j)%对于未给标号的点vj,当vivj为非饱和弧时No(j)=i;d(j)=C(

51、i,j)-f(i,j);pd=0;if(d(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;% 前向弧调整else