kruskal.txt

Kruskal避圈算法的matlab实现

%Kruskal避圈法的MATLAB程序代码如下：
n=6;
A=[
0	6	1	5	0	0	
6	0	5	0	3	0
1	5	0	5	6	4
5	0	5	0	0	2
0	3	6	0	0	6
0	0	4	2	6	0]; 
B=triu(A);%取A的上三角部分（无向图）
nonzone=find(B);%向量A中非零分量下标集
[k,l]=size(nonzone);	%显示A中所有正数的个数
for (i=1:k) x(i)=B(nonzone(i));end %向量A中非零分量组成的向量
[x,nonzone]=sortvector(n,x,nonzone);%排序

T(n,n)=0;	%将矩阵T中所有的元素赋值为0
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(zz,y)=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;		%假如TT中有圈
		else q=q+1;end;
    end;end;end;
end
T	%显示近似最小生成树T, 程序结束

function [a1,b1]=sortvector(n,a,b)%向量排序
[m,n]=size(a);
c=zeros(m,n);
for h=1:n-1
  for j=1:n-h
   if a(j)>a(j+1)
      t1=a(j);a(j)=a(j+1);a(j+1)=t1;  %从小到大排序
      t2=b(j);b(j)=b(j+1);b(j+1)=t2; %改变附属向量坐标
end
end
end
a1=a;
b1=b;