最小生成树(MATLAB)

prim算法设置两个集合P和Q，其中P用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P={V1}（假设构造最小生成树时，从顶点V1出发），集合Q的初值为。Prime算法的思想是，从所有p∈P，v∈V-P的边中，选取具有最小权值的边pv,将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到P=V时，最小生成树构造完毕，这时集合Q中包含了最小生成的所有边。（找最小的权，不连成圈即可）•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(a==0))=M;•result=[];p=1;tb=2:length(a);•whilelength(result)~=length(a)-1•temp=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))=[];•end•result•例、一个乡有7个自然村，其间道路如图所示，要以村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？Kruskal算法每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。•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;•[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=[];•whilelength(result)loop•temp=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)];•end•ifv1v2•index(find(index==v1))=v2;•else•index(find(index==v2))=v1;•end•data(:,flag)=[];•index(:,flag)=[];•end•result中国邮递员问题中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小的邮递路线叫做最优邮递路线。求图中所示的中国邮递员问题•Fleury算法（在一个Euler图中找出Euler环游）•注：包括三个文件；fleuf1.m,edf.m,flecvexf.m•function[Tc]=fleuf1(d)•%注：必须保证是Euler环游，否则输出T=0,c=0•n=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:n•ifmod(a(i),2)==1•m=m+1;•end•end•ifm~=0•fprintf('thereisnotexitEulerpath.\n')•T=0;c=0;•end•ifm==0•vet=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);Fleury算法—算法步骤：（１）任选一个顶点v0，令道路w0=v0（２）假定道路wi=v0e1v1e2…eivi已经选好，则从E\{e1,e2,…,ei}中选一条边ei+1，使：a）ei+1与vi相关联b）除非不能选择，否则一定要使ei+1不是Gi=G[E-{e1,e2,…,ei}]的割边．（３）第（２）步不能进行时就停止．•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)~=0•T=ed;•T(2,eds)=1;•c=0;•forg=1:eds•c=c+d(T(1,g),T(2,g));•end•flagg=0;•break;•end•end•end•end•function[flaged]=edf(matr,eds,vexs,ed,tem)•flag=1;•fori=2:eds•[dvexf]=flecvexf(matr,i,vexs,eds,ed,tem);•iff==1•flag=0;•break;•end•ifdvex~=0•ed(:,i)=[vexs(1,i)dvex];•vexs(1,i+1)=dvex;•matr(vexs(1,i+1),vexs(1,i))=0;•else•break;•end•end•function[dvexf]=flecvexf(matr,i,vexs,eds,ed,temp)•f=0;•edd=find(matr(vexs(1,i),:)==1);•dvex=0;•dvex1=[];•ded=[];•iflength(edd)==1•dvex=edd;•else•dd=1;dd1=0;kkk=0;•forkk=1:length(edd)•m1=find(vexs==edd(kk));•ifsum(m1)==0•dvex1(dd)=edd(kk);•dd=dd+1;•dd1=1;•else•kkk=kkk+1;•end•end•ifkkk==length(edd)•tem=vexs(1,i)*ones(1,kkk);•edd1=[tem;edd];•forl1=1:kkk•lt=0;ddd=1;•forl2=1:eds•ifedd1(1:2,l1)==ed(1:2,l2)•lt=lt+1;•end•end•iflt==0•ded(ddd)=edd(l1);•ddd=ddd+1;•end•end•end•iftemp=length(dvex1)•dvex=dvex1(temp);•elseiftemplength(dvex1)&temp=length(ded)•dvex=ded(temp);•else•f=1;•end•end旅行商问题的数学规划模型01(10)(.)s.t.1,()1,dijxijijdxijijijAxiVijjVxjijV设是与之间的距离，或表示连线，表示不连线.则有:min;每个点只有一条边出去；,()jV每个点只有一条边进入（除起点与终点外，各边不构成圈）或实例例从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)，五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113编写程序如下：clc,clear11,min..1,1,,.1,1,,||1,2||2,{1,2,,}{0,1},,1,,,.nijijijnijjnijiijijSijdxstxinxjnxSSnSnxijnij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(6,:)=0;a=a+a';c1=[51:46];L=length(c1);flag=1;whileflag0flag=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);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1));endcircle=c1;sum=sum1;c1=[561:4];%改变初始圈，该算法的最后一个顶点不动flag=1;whileflag0flag=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);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1));endifsum1sumsum=sum1;circle=c1;endcircle,sum