最小生成树MATLAB

《最小生成树MATLAB》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、..-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)

2、=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);•[,kb]=find(a(p,tb)==d);•j=p((1));k=tb(kb(1));•result=[result

3、,[j;k;d]];p=[p,k];tb(find(tb==k))=[];•end•result•例、一个乡有7个自然村，其间道路如下图，要以村为中心建有线播送网络，如要求沿道路架设播送线，应如何架设？..word.zl-..-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)=3

4、0;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)

5、1,flag)~=index(2,flag)•result=[result,data(:,flag)];•end•ifv1>v2•index(find(index==v1))=v2;..word.zl-..-•else•index(find(index==v2))=v1;•end•data(:,flag)=[];•index(:,flag)=[];•end•result中国邮递员问题中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。我们把增加重复边后不含奇点的新的连通

6、图叫做邮递路线，而总权最小的邮递路线叫做最优邮递路线。求图中所示的中国邮递员问题..word.zl-..-•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,e

7、ds+1);•matr=b;•fori=1:n•ifmod(a(i),2)==1•m=m+1;•end•end•ifm~=0•fprintf('thereisnotexitEulerpath.')•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);..word.zl-..-•matr(vexs(1,2),vexs(1,1))=

8、0;•flagg=1;tem=1;•whileflagg•[flagged]=edf(matr,eds,vexs,ed,tem);•tem=tem+1;•ifed(1,eds)~