www.gusucode.com > Floyd算法、dijkstra算法、贪婪算法、遗传算法、搜索算法、蚁群算法、哈密顿环路的matlab源程序 > code/搜索算法/liantong.m

    function w=liantong(D)
%使用广度优先搜索判断图是否连通
%D是01关联矩阵，且对角线元素为1
L=size(D,1);
FOUND=zeros(1,0);
%数据初始化
v=1;%当前节点集为第一个节点
FOUND=[FOUND,v];
%删除当前节点相互之间的关联边
D(v,v)=0;
%找当前节点的相邻节点
p=D(v,:);
vv=find(p==1);%当前节点的相邻的节点
if length(vv)==0
    w=0;
    return
end
%修正邻接矩阵
D(v,:)=zeros(1,L);
D(:,v)=zeros(L,1);
FOUND=[FOUND,vv];
while length(find(FOUND))<L
    v=vv;
    clear vv;
    LL=length(v);
    %第一步：删除当前节点相互间的关联边
    for i=1:LL
        for j=1:LL
            D(v(i),v(j))=0;
            D(v(j),v(i))=0;
        end
    end
    %第二步：找与当前节点的相邻接的节点
    vv=zeros(1,0);
    for i=1:LL
        p=D(v(i),:);
        pos=find(p==1);
        vv=[vv,pos];
    end
    if length(vv)==0%如果没有邻接节点，说明不连通
        w=0;
        return
    end
    %第三步：修正邻接矩阵
    for i=1:LL
        D(v(i),:)=zeros(1,L);
        D(:,v(i))=zeros(L,1);
    end
    FOUND=[FOUND,vv];
end
w=1;