iscycle.m

Kruskal求最小生成树算法 . 详细中文注释, 易于理解!

%iscycle.m
% 作者: 杨建栋%
% 日期: 2009年1月11日%
%判断加入新边后,是否构成循环
% 输入参数: korif = 节点集, 每次加入新边,需保证该边的两个节点标记相同.
%       akmi = 需要插入的新边
%输出参数: korif = 新节点集
%        c = 1 构成循环, 否则 c = 0
%---------------------------------------------------------
function [korif,c]=iscircle(korif,akmi)
g=max(korif)+1;
c=0;
n=length(korif);
%如果该边的两个节点都没有标记, 则标为g.
if korif(akmi(1))==0 & korif(akmi(2))==0
    korif(akmi(1))=g;
    korif(akmi(2))=g;
%如果该边的一个节点未标记,则将此节点做跟已标记的节点同样标记.
elseif korif(akmi(1))==0
    korif(akmi(1))=korif(akmi(2));
elseif korif(akmi(2))==0
    korif(akmi(2))=korif(akmi(1));
%如果该边的两个节点都已标记过,并且标记值相同,说明这两点已在同一连通区域中.则表示将出现循环
elseif korif(akmi(1))==korif(akmi(2))
    c=1;
    return
%如果该边的两个节点都已标记过,但是标记值不同,则把标记值中较大值改为较小值.
%即将两个连通区域相连成一个连通区域,这个连通区域中标记值较大的点改成标记值较小的
else
    m=max(korif(akmi(1)),korif(akmi(2)));
    for i=1:n
        if korif(i)==m
           korif(i)=min(korif(akmi(1)),korif(akmi(2)));
       end
   end
end