ｐrim算法设置两个集合P与Ｑ,其中P用于存放G得最小生成树中得顶点，集合Q存放Ｇ得最小生成树中得边。令集合Ｐ得初值为Ｐ＝{V1}(假设构造最小生成树时，从顶点V1出发),集合Q得初值为。Priｍe算法得思想就是,从所有p∈P,v∈V-Ｐ得边中,选取具有最小权值得边pｖ,将顶点v加入集合P中，将边pv加入集合Q中,如此不断重复，直到Ｐ=V时,最小生成树构造完毕,这时集合Q中包含了最小生成得所有边。(找最小得权,不连成圈即可)clｃ；ｃlear;Ｍ=1000;a(１,2)＝50;ａ（1,3）=6０;a（2，4)=６5;a（2,５)=４0;a(3,4)=52;a（3,７）=45;a（4,5)＝50;ａ(4,6)=30;a(4,7)＝４2;a(5，６)=70;a=［a;ｚeｒos（２,7)];a=a+a';a（ｆind（a==0))=Ｍ;result=［］;ｐ=1;ｔb=2:lengtｈ（a)；ｗhilelenｇth（resｕlｔ)～=leｎgtｈ(ａ)-１tｅmp=ａ（p,tｂ)；temp＝teｍｐ(:);d=mｉｎ(tｅmp);[jb,kb]=fｉｎd(a（p,tｂ)==d)；ｊ=ｐ(jb(1));k=tb(kb(１）)；ｒｅｓult=［ｒeｓｕｌt,［j；k;d]］;p=[ｐ,k］;ｔb（ｆiｎd(tb=＝k))=[];eｎdrｅsｕlt例、一个乡有7个自然村,其间道路如图所示,要以村为中心建有线广播网络,如要求沿道路架设广播线,应如何架设？Krｕskal算法每步从未选得边中选取边e,使它与已选边不构成圈,且e就是未选边中得最小权边,直到选够ｎ-1条边为止。clc;ｃleａr；M=100０;a(1,２)=50;a(1,3)=60;a(２,4)=65;a(2,5）=4０;ａ(3，4)=５2;a(3，7)=4５;a（4,５）＝5０;a(4,6)=３０;a(４,7)=４2；a（5，6）=70;[i,j]=ｆind((a～=0)＆(a~＝M))；b=a(fｉnd（（a~=0)＆（a～=M)));daｔa＝[i';j';ｂ'];inｄex=ｄａta(1:2,:);loop=max(ｓize（ａ))－１;ｒesｕｌt=［];whilｅleｎgtｈ(rｅｓuｌt)<looptemp=min(dａta（３,:）);fｌaｇ=finｄ(data(3,:)＝=temp);flag＝fｌag(１);v１=data(1,fｌａg);v2=dａｔa（２,ｆlag);ifiｎdex(1,flag)~=indeｘ(2，ｆlａg)ｒeｓｕlｔ＝[reｓult，data(:,flag)];eｎdifv1＞ｖ2ｉndex（ｆｉnd（iｎdex=＝v１）)=v２；ｅlseindex(ｆind（ｉndex==v2)）＝v１;eｎｄｄata(:,flaｇ)=［]；ｉndex(：，flag）=[］;endresｕlt中国邮递员问题中国邮递员问题也可以表示为:在一个有奇点得连通图中。要求增加一些重复边,使得新得连通图不含有奇点,并且增加得重复边总权最小。我们把增加重复边后不含奇点得新得连通图叫做邮递路线,而总权最小得邮递路线叫做最优邮递路线。求图中所示得中国邮递员问题Fleurｙ算法(在一个Ｅuｌeｒ图中找出Euleｒ环游)注:包括三个文件;fleｕｆ1、ｍ,ｅdf、m，ｆlecvｅxf、mfunction[Tc]=fleｕf1(d）%注:必须保证就是Eｕｌer环游,否则输出T=0,c＝0ｎ=ｌengtｈ(d);b=d;b(ｂ=＝ｉnｆ)=0;b(b~＝０)＝1;m＝０;a=suｍ(b);ｅds＝ｓum(a)/2；ed＝zeｒos（2，edｓ）；vexs=zｅros(1,eｄs+１）；ｍatr＝b;fori=１：nifｍｏd（ａ(ｉ）,2）==１m=ｍ+1;enｄenｄiｆm~=０ｆprinｔｆ('thereisnｏtexitEｕlerpａｔｈ、＼n＇)T=０;c=０；endiｆm==０vｅt=１;ｆlaｇ=0;ｔ1=ｆind（ｍａｔr(veｔ,:)＝=1)；forii＝１:lｅngth(t1）eｄ（:,１）=［vｅt,t1（iｉ)］;vｅｘs（１,1)=vet;vexs(1，2)=t1(ii）;matr(vｅxs(1,2),ｖeｘs(1，1))=0；flaｇg=1；tem=1;ｗｈilefｌaｇg[ｆlａgged］=edf(ｍａtr,ｅｄs,ｖexs,ed,tem)；ｔem=ｔem+1;ｉfed(1,edｓ)～=0＆ed(2,eｄs)~＝0T=ｅd;T（２,ｅds）＝1;c＝