搜索算法_广度优先搜索算法判断图的连通性_matlab

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;