mst_prim.txt.m

最小生成树

function MST_Prim(A)
b=length(A);
G=[A,ones(b,1)*10^9];
G=[G;ones(1,b+1)*10^9];
m=length(G);
for l=1:m
    G(l,l)=10^9;
end
n=input('输入初始城市号');
city=1:b;
road=[];
%形成树中城市序列和树外城市序列
if n==1
    in_city=1;
    out_city=city(1,2:b);
elseif n==b
    in_city=b;
    out_city=city(1,1:b-1);
else
    in_city=n;
    out_city=[city(1,1:n-1),city(1,n+1:b)];
end
for v=1:b-1
    GG=ones(m,m)*10000;
    Lin_city=length(in_city);
    %形成in_city和out_city的路程矩阵
    for i=1:Lin_city
        for j=1:b-1
            GG(in_city(i),out_city(j))=G(in_city(i),out_city(j));
        end
    end
    %寻找最短路径
    minGG=min(min(GG));
    [x,y]=find(minGG==GG);
    z=[x,y];
    if numel(z)>2
        z=z(1,:);
        y=y(1,1);
        x=x(1,1);
    end
    %将in_city和out_city矩阵近行相应替换
    in_city=[in_city,y];
    U=find(y==out_city);
    out_city(U)=m;
    length_road(v)=G(z(1),z(2));
    index_x(v)=x;
    index_y(v)=y;
end
index_road=[index_x',index_y'];
disp('依次被选路径序列')
disp(index_road)
disp('被选路径长度')
disp(length_road)