(图论)matlab模板程序.doc

《(图论)matlab模板程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一讲：图论模型程序一：可达矩阵算法%根据邻接矩阵A（有向图）求可达矩阵P（有向图）functionP=dgraf(A)n=size(A,1);P=A;fori=2:nP=P+A^i;endP(P~=0)=1;%将不为0的元素变为1P;程序二：无向图关联矩阵和邻接矩阵互换算法F表示所给出的图的相应矩阵W表示程序运行结束后的结果f=0表示把邻接矩阵转换为关联矩阵f=1表示把关联矩阵转换为邻接矩阵%无向图的关联矩阵和邻接矩阵的相互转换functionW=incandadf(F,f)iff==0%邻接矩阵转换为关联矩阵m=sum(sum(F))/2;%计算图的边数n=size(F,1);W=ze

2、ros(n,m);k=1;fori=1:nforj=i:nifF(i,j)~=0W(i,k)=1;%给边的始点赋值为1W(j,k)=1;%给边的终点赋值为1k=k+1;endendendelseiff==1%关联矩阵转换为邻接矩阵m=size(F,2);n=size(F,1);W=zeros(n,n);fori=1:ma=find(F(:,i)~=0);W(a(1),a(2))=1;%存在边，则邻接矩阵的对应值为1W(a(2),a(1))=1;endelsefprint('Pleaseimputtherightvalueoff');endW;程序三：有向图关联矩阵和邻接矩阵互换算法%有向图

3、的关联矩阵和邻接矩阵的转换functionW=mattransf(F,f)iff==0%邻接矩阵转换为关联矩阵m=sum(sum(F));n=size(F,1);W=zeros(n,m);k=1;fori=1:nforj=i:nifF(i,j)~=0%由i发出的边，有向边的始点W(i,k)=1;%关联矩阵始点值为1W(j,k)=-1;%关联矩阵终点值为-1k=k+1;endendendelseiff==1%关联矩阵转换为邻接矩阵m=size(F,2);n=size(F,1);W=zeros(n,n);fori=1:ma=find(F(:,i)~=0);%有向边的两个顶点ifF(a(1),i

4、)==1W(a(1),a(2))=1;%有向边由a(1)指向a(2)elseW(a(2),a(1))=1;%有向边由a(2)指向a(1)endendelsefprint('Pleaseimputtherightvalueoff');endW;第二讲：最短路问题程序0：最短距离矩阵W表示图的权值矩阵D表示图的最短距离矩阵%连通图中各项顶点间最短距离的计算functionD=shortdf(W)%对于W(i,j),若两顶点间存在弧，则为弧的权值，否则为inf；当i=j时W(i,j)=0n=length(W);D=W;m=1;whilem<=nfori=1:nforj=1:nifD(i,j)>D

5、(i,m)+D(m,j)D(i,j)+D(i,m)+D(m,j);%距离进行更新endendendm=m+1;endD;程序一：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

6、e(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)U(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu

7、=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