超全图论matlab程序 精品资料.doc

超全的图论程序程序一：可达矩阵算法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);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;程序三：有向图关联矩阵和邻接矩阵互换算法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;endendendelseiff==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;第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function[l,z]=Dijkstra(W)n=size(W,1);fori=1:nl(i)=W(1,i);z(i)=0;endi=1;whilei<=nforj=1:nifl(i)>l(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;ifj<ii=j-1;endendendi=i+1;end程序二：floyd算法（计算任意两点间的最短距离）function[d,r]=floyd(a)n=size(a,1);d=a;fori=1:nforj=1:nr(i,j)=j;endendr;fork=1:nfori=1:nforj=1:nifd(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[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(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(计算某点到其它所有点的最短距离)function[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]=pass2short(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<dt2d=dt1;P=[p1p2(2:length(p2))p3(2:length(p3))];elsed=dt1;p=[p4p5(2:length(p5))p6(2:length(p6))];endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法function[Tc]=krus