matlab 如何画出最小生成树(MST)

matlab 如何画出最小生成树(MST)
参考画凸壳(即凸包)、voronoi图、delaunay三角剖分的代码,写出画最小生成树的代码。(图中的点是用户点击的,这个不用管,已经写好了,任务就是根据这些点作出最小生成树的图)
提示:matlab对于这四种算法都有现成的函数(在下面参考代码中可以看见前三个的使用),matlab自带的最小生成树算法函数是 graphminspantree,可能会用到。

img


一种是避圈法

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