《matlab实现求图的连通分量算法.doc》由会员分享，可在线阅读，更多相关《matlab实现求图的连通分量算法.doc（3页珍藏版）》请在金锄头文库上搜索。
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;for i=1:N_TASK z(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; z(i).g
2、roupnumber=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_neighbors(8,9)=1;%使用递归的方法
3、对图进行先深搜索求图的连通分量z=dfs_main(z);%画点for i=1:N_TASK plot(z(i).x,z(i).y,k*); hold onend % 画出连线x1=z(1).x z(2).x;y1=z(1).y z(2).y;x2=z(2).x z(3).x;y2=z(2).y z(3).y;x3=z(1).x z(4).x;y3=z(1).y z(4).y;x4=z(5).x z(6).x;y4=z(5).y z(6).y;x5=z(5).x z(7).x;y5=z(5).y z(7).y;x6=z(8).x z(9).x;y6=z(8).y z(9).y;plot(x1,
4、y1,r*-);hold on plot(x2,y2,r*-);hold on plot(x3,y3,r*-);hold on plot(x4,y4,r*-);hold on plot(x5,y5,r*-);hold on plot(x6,y6,r*-);hold on grid onfunction results = dfs_main(z)k=0;for i=1:20; if(z(i).mark=0) k=k+1; fprintf(第%d个连通分量的顶点集为：n,k); z=dfs(z,i); fprintf(n); endendresults = z;function results = 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); end k=k+1; endresults=z;
