最小生成樹(MATLAB)

1、prim算法設(shè)置兩個集合P和Q，其中P 用于存放G的最小生成樹中的頂點，集合Q存放G的最小生成樹中的邊。令集合P的初值為P=V1（假設(shè)構(gòu)造最小生成樹時，從頂點V1出發(fā)），集合Q的初值為 。Prime算法的思想是，從所有p P，vV-P的邊中，選取具有最小權(quán)值的邊pv,將頂點v加入集合P中，將邊pv 加入集合Q中，如此不斷重復(fù)，直到P=V時，最小生成樹構(gòu)造完畢，這時集合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;a(3,7)=45; a(

2、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 例 、一個鄉(xiāng)有7個自然村，其間道路如圖所示，要

3、以村為中心建有線廣播網(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;b;index=data(1:2,:); loop=max(s

4、ize(a)-1; result=; while length(result)v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=; end result中國郵遞員問題中國郵遞員問題也可以表示為：在一個有奇點的連通圖中。要求增加一些重復(fù)邊，使得新的連通圖不含有奇點，并且增加的重復(fù)邊總權(quán)最小。我們把增加重復(fù)邊后不含奇點的新的連通圖叫做郵遞路線，而總權(quán)最小的郵遞路線叫做最優(yōu)郵遞路線。求圖中所示的中國郵遞員問題 Fleury算法（在一個Euler圖中找出Euler環(huán)游）

5、注：包括三個文件；fleuf1.m, edf.m, flecvexf.m function T c=fleuf1(d) %注：必須保證是Euler環(huán)游，否則輸出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; 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;

6、 end if m=0 vet=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 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

7、),T(2,g); end flagg=0; break; end end end end functionflag 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; end end function dvex f=flecvex

8、f(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; 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

9、=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