kruskal.m

最短路径问题（包括Floyd算法和避圈法）的matlab程序

a=[0 2 3 inf
   2 0 2 8
   3 7 0 2
   6 3 inf 0];
n=size(a,1);
k=1;   %记录a中不同正数的个数
for i=1:n-1
    for j=i+1:n   %查找循环中所以不同的正数
        if a(i,j)>0
            x(k)=a(i,j);  %数组x记录a中不同的正数
            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;   %显示a中所有不同的正数的个数
for i=1:k-1
    for j=i+1:k     %对a中的数进行排序（升序）
        if x(j)<x(i)
            xx=x(j);
            x(j)=x(i);
            x(i)=xx;
        end
    end
end
T(n,n)=0;  %T中所有元素赋值
q=0;    %记录加入到树T中的边数
for s=1:k
    if q==n
        break
    end   %获得最小生成树T，算法终止
    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);  %加边到T中去
                TT=T;   %临时记录T
                while 1
                    pd=1;  %去掉TT中所有的枝
                    for y=1:n
                        kk=0;
                        for z=1:n
                            if TT(y,z)>0
                                kk=kk+1;
                                zz=z;
                            end
                        end   %寻找TT中的树枝
                        if kk==1
                            TT(y,zz)=0;
                            TT(z,zz)=0;
                            pd=0;
                        end
                    end   %砍掉TT中的树枝
                    if pd
                        break
                    end
                end   %已砍掉了TT中的所有树枝
                pd=0;     %判断TT中是否有圈
                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
T   %显示近似最小生成树T，程序结束