图论matlab程序大全

图论程序大全程序一：可达矩阵算法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;ifjii=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;ifdt1dt2d=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]=krusf(d,flag)ifnargin==1n=size(d,2);m=sum(sum(d~=0))/2;b=zeros(3,m);k=1;fori=1:nforj=(i+1):nifd(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;fori=1:mift(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(1,i)),t(B(2,i)));forj=1:nift(j)==tmaxt(j)=tmin;endendendifk==nbreak;endendT;c;程序二：最小生成树的Prim算法function[Tc]=Primf(a)l=length(a);a(a==0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while(el)min=inf;fori=1:liflistV(i)==1forj=1:liflistV(j)==0&mina(i,j)min=a(i,j);b=a(i,j);s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=[source;destination];forg=1:e-1c(g)=a(T(1,g),T(2,g));endc;另外两种程序最小生成树程序1（prim算法构造最小生成树）a=[inf5060infinfinfinf;50infinf6540infinf;60infinf52infinf45;...inf6552inf503042;inf40inf50inf70inf;infinfinf3070infinf;...infinf4542infinfinf];result=[];p=1;tb=2:length(a);whilelength(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)=40;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=[];whilelength(result)looptemp=min(data(3,:));flag=find(data(3,:)==temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);ifindex(1,flag)~=index(2,flag)result=[result,data(:,flag)];endindex(find(index==v2))=v1;data(:,flag)=[];index(:,flag)=[];endresult第四讲：Euler图和Hamilton图程序一：Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m,edf.m,flecvexf.mfunction[Tc]=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=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;fori=1:nifmod(a(i),2)==1m=m+1;endendifm~=0fprintf('thereisnotexitEulerpath.\n')T=0;c=0;endifm==0vet=1;flag=0;t1=find(matr(vet,:)==1);forii=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;whileflagg[flagged]=edf(matr,eds,vexs,ed,tem);tem=tem+1;ifed(1,eds)~=0&ed(2,eds)~=0T=ed;T(2,eds)=1;c=0;forg=1:edsc=c+d(T(1,g),T(2,g));endflagg=0;break;endendendendfunction[flaged]=edf(matr,eds,vexs,ed,tem)flag=1;fori=2:eds[dvexf]=flecvexf(matr,i,vexs,eds,ed,tem);iff==1flag=0;break;endifdvex~=0ed(:,i)=[vexs(1,i)dvex];vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i))=0;elsebreak;endendfunction[dvexf]=flecvexf(matr,i,vexs,eds,ed,temp)f=0;edd=find(matr(vexs(1,i),:)==1);dvex=0;dvex1=[];ded=[];iflength(edd)==1dvex=edd;elsedd=1;dd1=0;kkk=0;forkk=1:length(edd)m1=find(vexs==edd(kk));ifsum(m1)==0dvex1(dd)=edd(kk);dd=dd+1;dd1=1;elsekkk=kkk+1;endendifkkk==length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=[tem;edd];forl1=1:kkklt=0;ddd=1;forl2=1:edsifedd1(1:2,l1)==ed(1:2,l2)lt=lt+1;endendiflt==0ded(ddd)=edd(l1);ddd=ddd+1;endendendiftemp=length(dvex1)dvex=dvex1(temp);elseiftemplength(dvex1)&temp=length(ded)dvex=ded(temp);elsef=1;enden