matlab下构建最小生成树

前文简单介绍了最悄锋铅小生成树的概念，下面在matlab中实际 *** 作一番。

在《图论——一个迷人的基念世界》这本书中，笔者找到了一个例启好题，如图1

首先我们使用先前介绍的Kruskal算法解题。

解：

选择图G中权值为5的最小权边v3v8,继续选择最小权边，v7v8和v3v7权值为7都可以入选，但是由于k>=2的条件（可以回看此算法定义），需要选取的边不能和之前最小权边组成圈，因此只能选一个，笔者选取v7v8。

有两条权为8的，都选择后会形成圈，因此选择一条加入T（所求的最小生成树），选择v3v4。

有两条权为9的，同样选v2v8，有两条权为10的，由于两条都加入也形不成圈，因此都加入。

有一条权为11的，然而选择它会形成圈，因此不选。

有三条权为12的，v5v6会导致出现圈，因此不能选择，选择v1v2或者v1v8都能得到一个最小生成树，选择v1v2。

得到T是一棵最小生成树，总权值为61，如图2所示

之后我们在matlab下进行求解：

根据图1的加权图G，在matlab中输入点和边的信息，

s = [1 1 2 2 3 3 3 4 4 4 5 6 7]

t = [2 8 3 8 4 7 8 5 6 7 6 7 8]

weights = [12 12 9 9 8 7 5 10 10 8 12 11 7]

G = graph(s,t,weights)

p = plot(G,'EdgeLabel',G.Edges.Weight)

通过指令minspantree即可求解

[T,pred] = minspantree(G)

highlight(p,T)

之后得到的图同样为总权值为61的最小生成树

给你个最小生成树的调御枯历用函数吧。将你的顶点数复制给n,邻接矩阵为W。然后调用mintree(n,W)

function [Wt,Pp]=mintree(n,W)

%求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示

%Wt是最小生成树的权败高，Pp（：，1：2）表示最小生成树镇搜的两顶点

%Pp(:，4)表示最小生成树的序号

tmpa=find(W~=inf)

[tmpb,tmpc]=find(W~=inf)

w=W(tmpa)

e=[tmpb,tmpc]

[wa,wb]=sort(w)

E=[e(wb,:),wa,wb]

[nE,mE]=size(E)

temp=find(E(:,1)-E(:,2))

E=E(temp,:)

P=E(1,:)

k=length(E(:,1))

while rank(E)>0

temp1=max(E(1,2),E(1,1))

temp2=min(E(1,2),E(1,1))

for i=1:k

if E(i,1)==temp1

E(i,1)=temp2

end

if E(i,2)==temp1

E(i,2)=temp2

end

end

a=find(E(:,1)-E(:,2))

E=E(a,:)

if rank(E)>0

P=[PE(1,:)]

k=length(E(:,1))

end

end

Wt=sum(P(:,3))

Pp=[e(P(:,4),:),P(:,3:4)]

for i=1:length(P(:,3))

disp(['','e',num2str(P(i,4)),'',...

'(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')'])

end

axis equal%画最小生成树

hold on

[x,y]=cylinder(1,n)

xm=min(x(1,:))

ym=min(y(1,:))

xx=max(x(1,:))

yy=max(y(1,:))

axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15])

plot(x(1,:),y(1,:),'ko')

for i=1:n

temp=['v',int2str(i)]

text(x(1,i),y(1,i),temp)

end

for i=1:nE

plot(x(1,e(i,:)),y(1,e(i,:)),'b')

end

for i=1:length(P(:,4))

plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r')

end

text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)])

title('红色连线为最小生成树')

axis off

hold off

function c1=Krusk(c,v0)

%最小生成树kruskal源腊兆做程序

%c:原图的邻接矩阵轮衡

%v0:根节点

%c1:最小生成树的邻接矩阵

[X,Y]=size(c)

if X~=Y

error('输入必须为方阵')

end

if v0>猜笑length(c(1,:))

error('不存在该顶点')

end

N=length(c(:,1))

con=0

c(find(c==0))=inf

c1=zeros(N,N)

comp=zeros(N,N)

comp(:,1)=[1:N]'

while con<N-1

clear min0

min0=min(min(c))

[x,y]=find(c==min0)

X=x(1)

Y=y(1)

c(X,Y)=inf

[i1,j1]=find(comp==X)

[i2,j2]=find(comp==Y)

if i1==i2

continue

else

l1=length(find(comp(i1,:)~=0))

l2=length(find(comp(i2,:)~=0))

comp(i1,[l1+1:l1+l2])=comp(i2,[1:l2])

comp(i2,:)=0

c1(X,Y)=min0

con=con+1

end

end

c1=c1'

---