matlab 如何画出最小生成树(MST)
参考画凸壳(即凸包)、voronoi图、delaunay三角剖分的代码,写出画最小生成树的代码。(图中的点是用户点击的,这个不用管,已经写好了,任务就是根据这些点作出最小生成树的图)
提示:matlab对于这四种算法都有现成的函数(在下面参考代码中可以看见前三个的使用),matlab自带的最小生成树算法函数是 graphminspantree,可能会用到。
一种是避圈法
function A = fun(W)
[m, n] = size(W);
e = 0;
for i = 1 : n
for j = i : n
if W(i, j) ~= 0
e = e + 1;
E(e, :) = [i, j, W(i, j)];
end
end
end
% sort W's edge by weight
for i = 1 : e - 1
for j = i + 1 : e
if E(i, 3) > E(j, 3)
temp = E(j, :);
E(j, :) = E(i, :);
E(i, :) = temp;
end
end
end
A = zeros(1, 3);
S = 1 : n;
for i = 1 : e
% if find-set(u) ~= find-set(v)
if S(E(i, 1)) ~= S(E(i, 2))
% A = A + (u, v)
A = cat(1, A, E(i,:));
%union(u, v)
indicator = S(E(i, 1));
for j = 1 : n
if S(j) == indicator
S(j) = S(E(i, 2));
end
end
end
end
A(1, :) = [];
例子:W=xlsread('C:UserspaulDesktop**.xls');
fun(W)
破圈法
function T=tree()
A=[inf 50 14 40 13;50 inf 15 20 inf;14 15 inf 10 20;40 20 10 inf 10;13 inf 20 10 inf];
n=5;
k=1;
for(i=1:n-1)
for(j=i+1:n)
if(A(i,j)>0)
x(k)=A(i,j);
kk=1;
for(s=1:k-1)
if(x(k)==x(s))
kk=0;
break;
end
end
k=k+kk;
end
end
end
k=k-1;
for(i=1:k-1)
for(j=i+1:k)
if(x(j)
xx=x(j);
x(j)=x(i);
x(i)=xx;
end
end
end
T(n,n)=0;
q=0;
for(s=1:k)
if(q==n)break;
end
for(i=1:n-1)
for(j=i+1:n)
if (A(i,j)==x(s))
T(i,j)=x(s);
T(j,i)=x(s);
TT=T;
while(1)pd=1;
for(y=1:n)kk=0;
for(z=1:n)
if(TT(y,z)>0)
kk=kk+1;
zz=z;
end;
end
if(kk==1)
TT(y,zz)=0;
TT(zz,y)=0;
pd=0;
end
end
if(pd)break;
end
end
pd=0;
for(y=1:n-1)
for(z=y+1:n)
if(TT(y,z)>0)pd=1;
break;
end
end
end
if(pd)
T(i,j)=0;
T(j,i)=0;
else q=q+1;
end
end
end
end
end