matlab实现求图的连通分量算法.doc

《matlab实现求图的连通分量算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、该算法主要是仿照c中利用先深搜索算法求图的连通分量的算法改写的。该算法假设有20个点，1号和2、4号相连，2号和3号相连，5号和6、7号相连，8号和9号相连，其他点都是孤立点。结果图如下：代码如下：clearN_TASK=20;%N_TASK任务的总个数%随机生成任务点的坐标x=rand(N_TASK,1);x=x*N_TASK;y=rand(N_TASK,1);y=y*N_TASK;fori=1:N_TASKz(i).x=x(i);z(i).y=y(i);z(i).mark=0;z(i).next=0;z(i).next(2)=0;z(i).next(3)=0;

2、z(i).groupnumber=0;end%使用z的next域表示点的下一个连接点z(1).next(1)=2;z(2).next(1)=3;z(1).next(2)=4;z(5).next(1)=6;z(5).next(2)=7;z(8).next(1)=9;%使用邻接矩阵表示点与点之间的链接关系z_neighbors=zeros(N_TASK,N_TASK);z_neighbors(1,2)=1;z_neighbors(2,3)=1;z_neighbors(1,4)=1;z_neighbors(5,6)=1;z_neighbors(5,7)=1;z_neig

3、hbors(8,9)=1;%使用递归的方法对图进行先深搜索求图的连通分量z=dfs_main(z);%画点fori=1:N_TASKplot(z(i).x,z(i).y,'k*');holdonend%画出连线x1=[z(1).xz(2).x];y1=[z(1).yz(2).y];x2=[z(2).xz(3).x];y2=[z(2).yz(3).y];x3=[z(1).xz(4).x];y3=[z(1).yz(4).y];x4=[z(5).xz(6).x];y4=[z(5).yz(6).y];x5=[z(5).xz(7).x];y5=[z(5).yz(7).y];

4、x6=[z(8).xz(9).x];y6=[z(8).yz(9).y];plot(x1,y1,'r*-');holdonplot(x2,y2,'r*-');holdonplot(x3,y3,'r*-');holdonplot(x4,y4,'r*-');holdonplot(x5,y5,'r*-');holdonplot(x6,y6,'r*-');holdongridonfunctionresults=dfs_main(z)k=0;fori=1:20;if(z(i).mark==0)k=k+1;fprintf('第%d个连通分量的顶点集为：{',k);z=dfs

5、(z,i);fprintf('}');endendresults=z;functionresults=dfs(z,i)fprintf('%d',i);z(i).mark=1;k=1;while(z(i).next(k)~=0)p=z(i).next(k);if(z(p).mark==0)z=dfs(z,p);endk=k+1;endresults=z;