最小生成树(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)=40;a(3,4)=52;a(3,7)=45;a(4,5)=5

2、0; a(4,6)=30;a(4,7)=42;?a(5,6)=70;a=a;zeros(2,7);a=a+a;a(fi nd(a=0)=M;result=;p=1;tb=2:le ngth(a);? while len gth(result)=le ngth(a)-1temp=a(p,tb);temp=temp(:);d=mi n(temp);jb,kb=fi nd(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result;k;d;p=p,k;tb(fi nd(tb=k)=;end? result? 例、一个乡有7个自然村，其间道路如图所示，要以村为中心建有线

3、广播网络，如要求沿道路架设广播线，应如何架设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=fi nd(a=0)&(a=M);? b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);? loop=max(size(a)-1;? resu

4、lt=;? while length(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag)=;endresult例如:endend中国邮递员问题中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一 些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小 的邮递路线叫做最优邮递路线。求图中所示的中国邮递员问题? Fleury 算法(在一个 Euler 图中找出 Euler 环游)Fleur

5、y 算法算法步骤 ：(1) 任选一个顶点 v0,令道路w0=v0(2) 假定道路 Wi=v0e1 v1e2eivi已经选好，则从e1,e2,ej中选一条边 ei+1 ，使：a) ei+1 与 vi 相关联b) 除非不能选择，否则一定要使ej+i不是Gj=GE-ei,e2,ei 的割边(3) 第(2)步不能进行时就停止.? 注：包括三个文件； , ,? function T c=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;

6、 ed=zeros(2,eds); vexs=zeros(1,eds+1); matr=b;for i=1:nif mod(a(i),2)=1 m=m+1;if m=0fprintf(there is not exit Euler path.n)T=0;c=0;endif m=0vet=1;flag=0;t1=find(matr(vet,:)=1);for ii=1:length(t1)ed(:,1)=vet,t1(ii);vexs(1,1)=vet;vexs(1,2)=t1(ii);matr(vexs(1,2),vexs(1,1)=0;flagg=1;tem=1;while flaggfla

7、gg ed=edf(matr,eds,vexs,ed,tem);tem=tem+1;if ed(1,eds)=0 & ed(2,eds)=0T=ed;T(2,eds)=1;c=0;for g=1:edsc=c+d(T(1,g),T(2,g);endflagg=0; break;endendfunctionflag ed=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:edsdvex f=flecvexf(matr,i,vexs,eds,ed,tem);if f=1flag=0;break;end if dvex=0ed(:,i)=vexs(1,i) dvex;v

8、exs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i)=0;elsebreak;endend? function dvex f=flecvexf(matr,i,vexs,eds,ed,temp)? f=0;? edd=find(matr(vexs(1,i),:)=1);? dvex=0;? dvex1=;? ded=;? if length(edd)=1? dvex=edd;elsedd=1;dd1=0;kkk=0;for kk=1:length(edd)m1=find(vexs=edd(kk);if sum(m1)=0dvex1(dd)=edd(kk);dd=d

9、d+1;dd1=1;elsekkk=kkk+1;endend if kkk=length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=tem;edd;for l1=1:kkklt=0;ddd=1;for l2=1:edsif edd1(1:2,l1)=ed(1:2,l2)lt=lt+1;endend if lt=0ded(ddd)=edd(l1);ddd=ddd+1;if temple ngth(dvexl) & temp0flag=0;for m=1:L-3for n=m+2:L-1if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)0flag=0;for m=1:L-3for n=m+2:L-1if a(c1(m),c1(n)+a(c1(m+1),c1(n+1).a(c1(m),c1(m+1)+