tree1.m

使用集合命令编写的图论最短路dijkstra算法的matlab程序

function [T,sum]=tree1(A)
%求连通图的最小生成树
%适用于无向图
%A=[0  8  11 1  5  2
%   8  0  6  12 7  3
%   11 6  0  9  10 4
%   1  12 9  0  3  5
%   5  7  10 3  0  6
%   2  3  4  5  6  0];
n=length(A);
k=1;
for i=1:n-1
    for j=i+1:n
        if A(i,j)>0
            x(k)=A(i,j);
            u(k)=i;%给出相应的边的端点的标号，标号与下标一样
            v(k)=j;
            k=k+1;
        end
    end
end
k=k-1;%边数
for i=1:k-1
    for j=i+1:k%按权从小到达排列边，相应的端点与标号跟着边移动
        if x(j)<x(i)
            xx=x(j);x(j)=x(i);x(i)=xx;
            uu=u(j);u(j)=u(i);u(i)=uu;
            vv=v(j);v(j)=v(i);v(i)=vv;
        end
    end
end
T=[];kk=0;sum=0;
for i=1:k
    if kk==n-1|x(i)==inf
        break;%n个顶点只需要n－1条边,如果边的权为无穷大则不需要继续
    else
        if u(i)==v(i)%选择的边的顶点标号相等，说明构成圈，不能添加
           continue;
        else sum=sum+x(i);T=[T;u(i),v(i)];%添加边
             kk=kk+1;
             m=max(u(i),v(i));%必须先赋值，不能直接在后面使用max(..)
             s=min(u(i),v(i));
            for j=1:n
                if u(j)==m%将添加的连通的顶点标号改成连通顶点标号的最小值
                   u(j)=s;
                end
                if v(j)==m
                   v(j)=s;
                end
            end
        end
    end
end
if kk<n-1
    fprintf('不是连通图')
end