最小生成树问题的matlab程序_CrazyMatrix

http://blog.sina.com.cn/u/2151795145

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

最小生成树问题的matlab程序

(2011-09-27 22:29:12)

标签：

matlab程序

最小生成树

分类：数学软件

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

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

E=E(a,:);

if rank(E)>0

P=[P;E(1,:)];

k=length(E(:,1));

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;

调用此程序要先编写主程序。

例：

n=6;

W=inf*ones(6);

W(1,[2,3,4])=[6,1,5];

W(2,[3,5])=[5,3];

W(3,[4,5,6])=[5,6,4];

W(4,6)=2;

W(5,6)=6;

[a,b]=mintree(n,W)

命名为example

在窗口中运行此程序得：

e2(v1v3)

e9(v4v6)

e6(v2v5)

e8(v1v4)

e3(v2v1)

a =

b =

1 3 1 2

4 6 2 9

2 5 3 6

3 6 4 8

2 3 5 3

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：合作对策问题的matlab程序

后一篇：matlab GUI封装（引用）

新浪BLOG意见反馈留言板　欢迎批评指正