资源描述：
《图的连通性判断matlab实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验三：图的连通性判断一、实验目的用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数，掌握Warshell算法或矩阵幂算法的实现方法。二、实验原理1、Warshell算法Warshell算法可解决图是否连通的问题,而且效率很高。在该算法中，矩阵是判断矩阵，表示从到连通，表示从到不连通。(1)置新矩阵P:=C;(2)置=1;(3)对所有的,若,则对k=1,2,…,n,有;(4);(5)如转向步骤(3),否则停止。2、矩阵幂算法由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。可
2、以通过对邻接阵C做一些计算，得到图G的一些性质。例如考虑中的的元素，如果它不为零，由于，则至少存在一组或一个长度为3的链使端和端相连。从而，通过计算C的各阶幂次可得到关于图是否连通的信息。三、实验内容1.利用MATLAB等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通分支数的判断。2.比较Warshell算法和矩阵幂算法在算法正确性和算法复杂度上的区别。3.对算法进行优化。四、采用的语言MatLab源代码：clear,clc;%输入邻接矩阵disp('图的连通性以及连通分支数的判断');C=input('请输入
3、图的邻接矩阵(格式如：[110;111;011])C=');%矩阵幂算法n=size(C,1);%邻接矩阵阶数P=zeros(n,n);%构造连通矩阵Pk=1;fork=1:n%计算矩阵幂的和C1=C^k;P=P+C1;endS=n-rank(P);%连通分支数为0特征值个数%Warshell算法S1=0;a=1;G=zeros(n,1);fori=1:nforj=(i+1):nifC(i,j)==1%若两端之间有边连通ifG(i)==G(j)%若两端之间有连通链，说明二者在同一连通分支ifG(i)==0G(i)=a;G(j)
4、=a;a=a+1;S1=S1+1;endelseifG(i)==0G(i)=G(j);%若与i不连通，则与j在同一连通分支elseifG(j)==0G(j)=G(i);%若与j不连通，则与i在同一连通分支else%若两端相连通，但标记在不同连通分支，合并两连通分支forb=1:nifG(b)==G(i)G(b)=G(j);%合并两连通分支endendS1=S1-1;%合并两连通分支endendendendend%输出结果CifS==1disp('矩阵幂算法：连通');elsedisp(['矩阵幂算法:不连通，连通分支数=',n
5、um2str(S)]);endifS1==1disp('Warshell算法：连通');elsedisp(['Warshell算法：不连通，连通分支数=',num2str(S1)]);end五、数据结构1.主要函数输入函数：C=input('输入图的邻接矩阵C=');矩阵幂算法：n=size(C,1);%邻接矩阵阶数P=zeros(n,n);%连通矩阵Pk=1;fork=1:n%计算矩阵幂的和C1=C^k;P=P+C1;endS=n-rank(P);%连通分支数为0特征值个数Warshell算法：S1=0;a=1;G=zero
6、s(n,1);fori=1:nforj=(i+1):nifC(i,j)==1%若两端之间有边连通ifG(i)==G(j)%若两端之间有连通链，说明二者在同一连通分支ifG(i)==0G(i)=a;G(j)=a;a=a+1;S1=S1+1;endelseifG(i)==0G(i)=G(j);%若与i不连通，则与j在同一连通分支elseifG(j)==0G(j)=G(i);%若与j不连通，则与i在同一连通分支else%若两端相连通，但标记在不同连通分支，合并两连通分支forb=1:nifG(b)==G(i)G(b)=G(j);%合
7、并两连通分支endendS1=S1-1;%合并两连通分支endendendendend输出函数：CifS==1disp('矩阵幂算法：连通');elsedisp(['矩阵幂算法：不连通，连通分支数=',num2str(S)]);endifS1==1disp('Warshell算法：连通');elsedisp(['Warshell算法：不连通，连通分支数=',num2str(S1)]);end2.算法的流程图矩阵幂算法：YesNoC1=C^kP=P+C1k=k+1得到C的阶数nk=1开始输入邻接矩阵Ck<=n?连通分支数S=n-
8、连通矩阵P的秩结束Warshell算法：i++若p(j,i)=1p(i,j)=p(i,k)+*p(k,j)j++i=1,j=1输入邻接矩阵C得到C的阶数n边数mk=1开始i<=n?j<=i?YesNoYesNo结束连通分支数S六、实验结论与分析Warshell算法和矩阵幂算法
