资源描述：
《图论在matlab中的实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论在matlab中的实现最短路问题例某公司在六个城市中有分公司，从ci到cj的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。用矩阵（为顶点个数）存放各边权的邻接矩阵，行向量pb、index1、index2、d分别用来存放标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量index2(i)存放始点到第点最短通路中第顶点前一顶点的序号；d(i)存放由始点到第点最短通路的值。Dijkstra的Matlab程序如下：M=100
2、00;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);a=a+a';pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));d(1:length(a))=M;d(1)=0;temp=1;
3、whilesum(pb)=2index=index(1);endindex2(temp
4、)=index;endd,index1,index2Floyd算法的Matlab程序如下：clear;clc;M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);b=a+a';path=zeros(length(b));fork=1:6f
5、ori=1:6forj=1:6ifb(i,j)>b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,path最小生成树问题prim算法如下：clc;clear;M=1000;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;a=[a;zeros(2,7)];a=a+a';a(find(
6、a==0))=M;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))=[];endresultKruskal算法如下：clc;clear;M=1000;a(1,2)=
7、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]=find((a~=0)&(a~=M));b=a(find((a~=0)&(a~=M)));data=[i';j';b'];index=data(1:2,:);loop=max(size(a))-1;result=[];用存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号改记为此边的另一
8、序号，同时把后面边中所有序号为的改记为。此方法的几何意义是：将序号的这个顶点收缩到顶点，顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。whilelength(result)
