tree2.m

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

function [T,sum]=tree2(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);
for i=1:n
    l(i)=i;%给出相应的边的端点的标号，标号与下标一样
    A(i,i)=inf;%因为用对矩阵求最小值的方法找最小边，所以改写对角线的0
end
sum=0;kk=0;T=[];
while kk<n-1%n个顶点只需要n－1条边
    min_e=min(min(A));
    if min_e==inf
    fprintf('不是连通图')
    break;
    end
    for i=1:n-1
    for j=i+1:n
        if A(i,j)==min_e
            if l(i)~=l(j)%不构成圈
                sum=sum+min_e;T=[T;i,j];
                 A(i,j)=inf;A(j,i)=inf;%被选中的边更改数据避免重复选择
                 m=max(l(i),l(j));%必须先赋值，不能直接在后面使用max(..)
                 s=min(l(i),l(j));
                 for k=1:n
                     if l(k)==m
                        l(k)=s;%将添加的连通的顶点标号改成连通顶点标号的最小值
                     end
                 end
                 kk=kk+1;
                 break;%添加了一条边后必须跳到while寻找全矩阵最小值（否则只是在i行找）
             else
            A(i,j)=inf;A(j,i)=inf;%构成圈的边不选择，改变数据
             end
          end
    end
    if A(i,j)==min_e&l(i)~=l(j)
        break;%添加了一条边，帮助跳出for循环回到while循环
    end
    end
end
l%l最后应该变成全1向量，否则不是连通图或者程序出错