最小生成树（MATLAB）

1、 PAGE9 / NUMPAGES9 prim算法设置两个集合P和Q，其中P 用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P=V1（假设构造最小生成树时，从顶点V1出发），集合Q的初值为。Prime算法的思想是，从所有p P，vV-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;

2、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);while length(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,j;k;d;p=p,k;tb(find(tb=k)=;endresult例 、一个乡有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=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;re

4、sult=;while length(result)v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=;endresult中国邮递员问题中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小的邮递路线叫做最优邮递路线。求图中所示的中国邮递员问题Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m

5、, edf.m, flecvexf.mfunction T c=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0n=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;for i=1:n if mod(a(i),2)=1 m=m+1; endendif m=0 fprintf(there is not exit Euler path.n) T=0;c=0;endif m=0 vet=1; flag=0; t1=find

6、(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 flagg flagg ed=edf(matr,eds,vexs,ed,tem); tem=tem+1; if ed(1,eds)=0 & ed(2,eds)=0 T=ed; T(2,eds)=1; c=0; for g=1:eds c=c+d(T(1,g),T(2,g); end flagg=0; break; end

7、end endendfunctionflag ed=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:eds dvex f=flecvexf(matr,i,vexs,eds,ed,tem); if f=1 flag=0; break; end if dvex=0 ed(:,i)=vexs(1,i) dvex; vexs(1,i+1)=dvex; matr(vexs(1,i+1),vexs(1,i)=0; else break; endendfunction dvex f=flecvexf(matr,i,vexs,eds,ed,temp)f=0;edd=find(m

8、atr(vexs(1,i),:)=1);dvex=0;dvex1=;ded=;if length(edd)=1 dvex=edd;else dd=1;dd1=0;kkk=0; for kk=1:length(edd) m1=find(vexs=edd(kk); if sum(m1)=0 dvex1(dd)=edd(kk); dd=dd+1; dd1=1; else kkk=kkk+1; end end if kkk=length(edd) tem=vexs(1,i)*ones(1,kkk); edd1=tem;edd; for l1=1:kkk lt=0;ddd=1; for l2=1:eds if edd1(1:2,l1)=ed(1:2,l2) lt=lt+1; end end if lt=0 ded(ddd)=edd(l1); ddd=ddd+1; end end end if templength(dvex1) & temp0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1). a(c1(m),c1(m+1)+a(c1(n),c1(n+