1、精選優(yōu)質(zhì)文檔-傾情為你奉上prim算法設(shè)置兩個(gè)集合P和Q，其中P 用于存放G的最小生成樹中的頂點(diǎn)，集合Q存放G的最小生成樹中的邊。令集合P的初值為P=V1（假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn)V1出發(fā)），集合Q的初值為 。Prime算法的思想是，從所有p P，vV-P的邊中，選取具有最小權(quán)值的邊pv,將頂點(diǎn)v加入集合P中，將邊pv 加入集合Q中，如此不斷重復(fù)，直到P=V時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合Q中包含了最小生成的所有邊。（找最小的權(quán)，不連成圈即可） 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); 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 例 、一個(gè)鄉(xiāng)

3、有7個(gè)自然村，其間道路如圖所示，要以村為中心建有線廣播網(wǎng)絡(luò)，如要求沿道路架設(shè)廣播線，應(yīng)如何架設(shè)？Kruskal算法 每步從未選的邊中選取邊e，使它與已選邊不構(gòu)成圈，且e是未選邊中的最小權(quán)邊，直到選夠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

4、9;b'index=data(1:2,:); loop=max(size(a)-1; result=; while length(result)<loop temp=min(data(3,:); flag=find(data(3,:)=temp); flag=flag(1); v1=data(1,flag);v2=data(2,flag); if index(1,flag)=index(2,flag) result=result,data(:,flag); end if v1>v2 index(find(index=v1)=v2; else index(find(index

5、=v2)=v1; end data(:,flag)=; index(:,flag)=; end result中國郵遞員問題中國郵遞員問題也可以表示為：在一個(gè)有奇點(diǎn)的連通圖中。要求增加一些重復(fù)邊，使得新的連通圖不含有奇點(diǎn)，并且增加的重復(fù)邊總權(quán)最小。我們把增加重復(fù)邊后不含奇點(diǎn)的新的連通圖叫做郵遞路線，而總權(quán)最小的郵遞路線叫做最優(yōu)郵遞路線。求圖中所示的中國郵遞員問題 Fleury算法（在一個(gè)Euler圖中找出Euler環(huán)游） 注：包括三個(gè)文件；fleuf1.m, edf.m, flecvexf.m function T c=fleuf1(d) %注：必須保證是Euler環(huán)游，否則輸出T=0,c=0

6、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,eds+1); matr=b; for i=1:n if mod(a(i),2)=1 m=m+1; end end if m=0 fprintf('there is not exit Euler path.n') T=0;c=0; end if m=0 vet=1; flag=0; t1=find(matr(vet,:)=1); for ii=1:length(t1) ed(:,1)

7、=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 end end end functionflag ed=edf(matr,eds

8、,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; end end function dvex f=flecvexf(matr,i,vexs,eds,ed,temp) f=0; edd=find(matr(vexs(1,i),:)=1); dvex=0; dve

9、x1=; 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)

10、 lt=lt+1; end end if lt=0 ded(ddd)=edd(l1); ddd=ddd+1; end end end if temp<=length(dvex1) dvex=dvex1(temp); elseif temp>length(dvex1) & temp<=length(ded) dvex=ded(temp); else f=1; end end旅行商問題的數(shù)學(xué)規(guī)劃模型或?qū)嵗?從北京（Pe）乘飛機(jī)到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)，五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間

11、的航線距離如下表： LMNPaPeTL 5635215160M56 21577870N3521 366868Pa215736 5161Pe51786851 13T6070686113 編寫程序如下：clc,cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=

12、0;a=a+a'c1=5 1:4 6;L=length(c1);flag=1;while flag>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+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end endendendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endcircle=c1;sum=sum1;c1=5 6 1:4;%改變初始圈，該算法的最后一個(gè)頂點(diǎn)不動(dòng)flag=1;while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c