超全图论matlab程序.pdf

《超全图论matlab程序.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、超全的图论程序关注微信公众号“超级数学建模”，教你做有料、有趣的数模人程序一：可达矩阵算法functionP=dgraf(A)n=size(A,1);P=A;fori=2:nP=P+A^i;endP(P~=0)=1;P;程序二：关联矩阵和邻接矩阵互换算法functionW=incandadf(F,f)iff==0m=sum(sum(F))/2;n=size(F,1);W=zeros(n,m);k=1;fori=1:nforj=i:nifF(i,j)~=0W(i,k)=1;W(j,k)=1;k=k+1;endendendelseiff==1m=size(F,

2、2);n=size(F,1);W=zeros(n,n);fori=1:ma=find(F(:,i)~=0);W(a(1),a(2))=1;W(a(2),a(1))=1;endelsefprint('Pleaseimputtherightvalueoff');endW;1程序三：有向图关联矩阵和邻接矩阵互换算法functionW=mattransf(F,f)iff==0m=sum(sum(F));n=size(F,1);W=zeros(n,m);k=1;fori=1:nforj=i:nifF(i,j)~=0W(i,k)=1;W(j,k)=-1;k=k+1;e

3、ndendendelseiff==1m=size(F,2);n=size(F,1);W=zeros(n,n);fori=1:ma=find(F(:,i)~=0);ifF(a(1),i)==1W(a(1),a(2))=1;elseW(a(2),a(1))=1;endendelsefprint('Pleaseimputtherightvalueoff');endW;2第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function[l,z]=Dijkstra(W)n=size(W,1);fori=1:nl(i)=W(1,i);z(i)=0;

4、endi=1;whilei<=nforj=1:nifl(i)>l(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;ifj

5、endend程序三：n2short.m计算指定两点间的最短距离function[Pu]=n2short(W,k1,k2)n=length(W);U=W;m=1;whilem<=nfori=1:nforj=1:nifU(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;whilekk~=k1fori=1:nV(1,i)=U(k1,kk)-W(i,kk);ifV(1,i)==U(

6、k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=find(P1~=0);forj=length(wrow):-1:1P(k)=P1(wrow(j));k=k+1;endP;程序四、n1short.m(计算某点到其它所有点的最短距离)4function[PmD]=n1short(W,k)n=size(W,1);D=zeros(1,n);fori=1:n[Pd]=n2short(W,k,i);Pm{i}=P;D(i)=d;end程序五：pass2short.m(计算经过某两点的最短距离)function[Pd]=pass

7、2short(W,k1,k2,t1,t2)[p1d1]=n2short(W,k1,t1);[p2d2]=n2short(W,t1,t2);[p3d3]=n2short(W,t2,k2);dt1=d1+d2+d3;[p4d4]=n2short(W,k1,t2);[p5d5]=n2short(W,t2,t1);[p6d6]=n2short(W,t1,k2);dt2=d4+d5+d6;ifdt1

8、length(p6))];endP;d;5第三讲：最小生成树程序一