%Kruskal算法求最小生成树和最小总费用
%Example5表示距离矩阵的上三角块
%graph_adjacent表示距离矩阵
load Example5
graph_adjacent=Example5+Example5'
len=length(graph_adjacent);%计算图中的顶点数
temp=graph_adjacent;%将原图内容拷贝到temp中,以防对原图做改动
superedge=zeros(len-1,2);%用于保存生成最小生成树的边
i=1;%指向superedge的下标
for j=1:len
tag(j)=j;%关联标志初始化,将每个顶点的关联标志设为其本身
end;
%以下的循环完成kruskal算法
while(superedge(len-1,1)==0)
[Y,I]=sort(temp);%将temp的每列按从小到大排序,数组Y保存temp 排序后的结果,I中保存相应结果对应的在temp中的下标
cost_min=min(Y(1,:));%找出权值最小的边
index=find(Y(1,:)==cost_min);%找出权值最小的边对应的顶点
index=index(1);%一条边对应两个节点,且不同的边的权值可能一样,这里为了方便处理人为规定了顺序,取标号最小的顶点进行处理
anotherpoint=I(1,index);%找到该边对应的另一个顶点
%将该边对应的权值修改为最大,防止该边在下次循环中再次被选为最优边
temp(index,anotherpoint)=100;
temp(anotherpoint,index)=100;
if(tag(anotherpoint)~=tag(index))%当两个点不属于一个连通集时,这两个点之间的边为最小生成树的边
superedge(i,:)=[index,anotherpoint];%将其加入最小生成树的边集中
i=i+1;%下标加1
%下面的语句的作用是将两个连通分支变成一个连通分支,即tag值一样
for j=1:len%以index的tag值为标准
if((tag(j)==tag(anotherpoint))&(j~=anotherpoint))%遍搜tag数组,先将和anotherpoint tag值一样的点的tag值变为index的tag值
tag(j)=tag(index);
end
end
tag(anotherpoint)=tag(index);%将anotherpoint的tag值变为index的tag值
end
end
%*************************结果显示模块************************************
s=0;
for ii=1:len-1
k=sprintf('最小生成树第%d条边:(%d,%d),权值为%d',ii,superedge(ii,1),superedge(ii,2),graph_adjacent(superedge(ii,1),superedge(ii,2)));%格式化字符串
disp(k);%显示
disp(' ');%空一行
s=s+graph_adjacent(superedge(ii,1),superedge(ii,2)); %求最小生成树的代价
end
%显示最小生成树的代价
disp('最小生成树的总代价为:')
disp(s);
评论0