图论各种算法matlab实现.doc

《图论各种算法matlab实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Floyd算法clear;clc;n=6;a=zeros(n);a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;a(4,5)=10;a(4,6)=25;a(5,6)=55;a=a+a';M=max(max(a))*n^2;%MΪ³ä·Ö´óµÄÕýʵÊýa=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)

2、+a(k,j);path(i,j)=k;endendendenda,pathHamilton算法functionmainclc,clearglobalaa=zeros(6);a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a=a+a';L=size(a,1);c1=[51:46];[circle,long]=modifycir

3、cle(c1,L);c2=[561:4];%¸Ä±ä³õʼȦ£¬¸ÃËã·¨µÄ×îºóÒ»¸ö¶¥µã²»¶¯[circle2,long2]=modifycircle(c2,L);iflong2

4、lobalaflag=1;whileflag>0flag=0;form=1:L-3forn=m+2:L-1ifa(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...a(c1(m),c1(m+1))+a(c1(n),c1(n+1))flag=1;c1(m+1:n)=c1(n:-1:m+1);endendendendlong=a(c1(1),c1(L));fori=1:L-1long=long+a(c1(i),c1(i+1));endcircle=c1;Kruskal算法clc;clear;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,

5、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)

6、g)result=[result,data(:,flag)];endindex(find(index==v2))=v1;data(:,flag)=[];index(:,flag)=[];endresultPrim算法clc;clear;a=zeros(7);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+a';a(find(a==0))=inf;result=[];p=1;tb=2:length(a);whilele

7、ngth(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