《最小生成树.doc》由会员分享，可在线阅读，更多相关《最小生成树.doc（12页珍藏版）》请在三一文库上搜索。
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);? while length(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)=;end? result? 例
3、 、一个乡有 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=dat
4、a(1:2,:);? loop=max(size(a)-1;? result=;? while length(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag)=;endresult中国邮递员问题中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小 的邮递路线叫做最优邮递路线。求图中所示的中国邮递员问题? Fleury 算法（在一个
5、 Euler 图中找出 Euler 环游）Fleury 算法算法步骤 ：（）任选一个顶点 v0，令道路 w0=v 0（）假定道路 wi=v0e1v1e2eivi 已经选好，则从 e1,e2, ,ei 中选一条边 ei+1 ，使：a） ei+1 与 vi 相关联 b）除非不能选择，否则一定要使ei+1 不是 Gi =G E- e1,e2, ,ei 的割边（）第（）步不能进行时就停止? 注：包括三个文件； , ,? function T c=fleuf1(d)? %注：必须保证是 Euler 环游，否则输出 T=0,c=0? n=length(d);? b=d;? b(b=inf)=0;? b(b
6、=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: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
7、,1)=0;flagg=1;tem=1;while flaggflagg 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);end flagg=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;en
8、d if dvex=0ed(:,i)=vexs(1,i) dvex;vexs(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)
9、;if sum(m1)=0dvex1(dd)=edd(kk);dd=dd+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 templength(dvex1) & 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)+a(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);endendendendsum1=0;for i=1:L-1sum1=sum1+a(c1(i),c1(i+1);endif sum1sumsum=sum1;circle=c1;endcircle,sum