北邮信息工程通信网理论基础实验3报告——图的连通性

1、通信网理论基础实验报告信息与通信工程学院通信网理论基础实验报告班级： 姓名： 学号： 序号： 日 期： 第10页 实验三图的连通性判断一、实验目的本次实验要求用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数，使学生掌握warshell算法或矩阵幂算法的实现方法，培养算法设计与优化能力。二、 实验原理1、warshall算法warshall算法可解决图是否连通的问题, 而且效率很高。在该算法中，矩阵 是判断矩阵，表示从到 连通，表示从到不连通。(1)置新矩阵p:= c;(2)置 = 1; (3)对所有的, 如果pj,i=1 , 则对k=1,2,n ;(

2、4) ;(5) 如 转向步骤(3), 否则停止。2、矩阵幂算法由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。可以通过对邻接阵c做一些计算，得到图g的一些性质。例如考虑中的的元素 ，如果它不为零，由于，则至少存在一组或一个长度为3的链使端和端j相连。从而，通过计算c的各阶幂次可得到关于图是否连通的信息。3、算法分析对于算法，基本问题是算法的正确性，其次是算法复杂度。从复杂度考虑，算法可以简单分为多项式复杂度和指数复杂度两大类，前者的目标是找到尽可能小的复杂度算法；后者的目标是找到合适的近似算法。三、 实验内容(1) 两人一组，利用matlab等语言实现图的连通性判断算法，可对输入的

3、邻接阵进行连通性以及连通分支数的判断。(2) 比较warshall算法和矩阵幂算法在算法正确性和算法复杂度上的区别。(3) 对算法进行优化。四、程序基本信息1、设计语言及开发工具：matlab。2、数据结构：本次实验由于算法简单，每次计算的数据之间也不存在任何关系（独立）的，因此程序设计时只采用了诸如串、数组等简单形式用于存储数据，复杂的数据结构思想诸如链表、树等基本没有采用。3、主要函数（算法）：本程序采用matlab语言编写，包含2个主要的m文件。（1）generatematrix.m文件这个函数随机产生一个邻接矩阵，代码比较简单不作过多介绍。因为本次设计的算法主要用于无向图，因此生成的矩

4、阵是对称的方阵。（2）connectivity.m文件主程序，包含四个通过分析输入的邻接矩阵判断图连通性的算法，程序也被分成四部分。除了第一部分以外，其它三个部分都是判断图的连通性的算法，并可统计算法运行时间。第一部分：判断图的连通分支数该算法的主要思想是根据端与端的连接关系把各端点进行归类，每一类即一个连通分支。具体见下页的流程图。理论复杂度为。第二部分：矩阵幂算法算法原理：通过计算矩阵的各阶幂次可得到关于图是否连通的信息。有如下定理：若，则i 节点和j 节点间没有路径相通。根据该定理可得到如下利用矩阵幂算法判定图的连通性的准则：对于矩阵，如果矩阵s 中的元素全部为非零元素，则图g 为连通图

5、；否则如果矩阵s 中存在t(t 1)个零元素，则图g 为非连通图。判定连通分支算法的流程图该算法基于以上判定准则编写，判定一个用n阶邻接矩阵表示的图的连通性，它的2次幂、3次幂一直到n次幂都需要计算，因此花费时间总体来说是所有算法中最长的。由于要求从2到n次幂，每次计算矩阵幂的复杂度为，因此理论复杂度为（更准确的表述是）。第三部分：矩阵幂算法（改进）根据矩阵幂算法的原理，需要计算多次矩阵幂且把每次的结果相加，最后的矩阵只需满足每个元素值大于零即可。针对这一点，我想了两个方面的优化办法：第一：只计算矩阵幂中特定位置的元素值。邻接矩阵及其矩阵幂中，若0，表明端和端j已经相连，也就是说在接下来判定的

6、过程中，这些元素都是不必考虑的。由此，若邻接矩阵中位置元素为0，只需计算矩阵幂中 位置的元素值，若不为0则可判定端和端j相连。这种计算方法可用公式表示如下（该公式是前面给出的3阶矩阵幂元素值公式的拓展）：可见，实现该公式，需要考虑这n-1个元素中每个元素取值1m（m为矩阵阶数）的所有情况，简单的说就是要实现次循环。由于matlab没有类似c语言中goto的语句，所以要实现这个公式可以说是非常困难。当然并非完全不可以，例如利用其它语言控制matlab的循环语句执行次数等等，但是由于难度较大加之时间有限，我最终没有采用这个优化方案。第二：减少矩阵幂的计算次数。这个方案非常简单，实现起来也容易得多。

7、原算法首先计算矩阵的2到n次幂，再按所有幂相加之后的矩阵判断，事实上，只要有一次矩阵幂算法的结果矩阵所有元素均大于0，那么就可判定原图连通，算法终止。由此，每执行一次矩阵幂算法，就判断结果矩阵所有元素是否均大于0。这样很多时候可以减少计算量。当然必须要说明的是，这种方案在减少计算次数的同时，增加了判定的次数。因此对于阶数较小的邻接阵的判定，使用该算法反而会增加执行时间，但是对于复杂矩阵的判定（阶数大于10）时就会呈现效果。对于特别复杂的矩阵（阶数大于20），执行时间可以被极大的减小，甚至小于warshall算法的执行时间，但是很复杂的图并不多见，这也说明它的实用性不是很强，因此它只能算作对原算

8、法的一个改进，而不能称之为完全的优化。而且以上理论都是对于连通图而言的，对于非连通图，该算法反而会增加复杂度。改进后的算法复杂度与矩阵幂算法相同，之所以实现了优化是因为它的n值是很小的。第四部分：warshall算法算法的原理和流程前面已有描述，这里不再重复。理论复杂度为。需要说明的是经过warshall算法处理后输出的是和邻接矩阵类似的判断矩阵，大多数连通图的输出结果是一个全为1的矩阵，但少数情况不是。在这里，本程序简单的按照输出矩阵是否所有元素均为1来判断连通性，某些情况下会出现判定错误的情况。warshall算法本身已经是一个复杂度极低的算法，但它也拥有自己的优化算法，同样是通过减少或运

9、算次数来实现的。由于它的效果不是很明显，我没有采用。五、程序运行结果与分析1、简单矩阵运行结果：以下给出简单图的邻接矩阵，它们均为4阶方阵，主要用来说明算法的正确性。图1（连通图）：邻接矩阵：g= 程序运行结果：图2（非连通图）：邻接矩阵：g=程序运行结果：2、复杂矩阵运行结果：以下使用generatematrix函数随机生成几个较为复杂的邻接矩阵，主要用来说明算法的执行时间（复杂度）：图1：8阶邻接矩阵，非连通图：图2：30阶邻接矩阵，连通图由以上截图可见，随着矩阵复杂增加，改进后的矩阵幂算法执行时间是有可能小于warshall算法的。六、 遇到的主要问题 这次实验出现的问题基本上集中在算法

10、判定结果不正确这个方面。1、判断连通分支算法：开始设计算法时，在对端点进行归类后立即进行连通分支的判断，也就是发现新的连通分支后先让连通分支数加一，然后若判断出该连通分支与图的其它部分实际是相连的时候再让连通分支数减一。实际运行时却发现输出结果往往是错误的。于是修改算法让其直接按端点归类的情况进行判断。2、矩阵幂算法：算法本身是很简单的，但是在一开始我对判定准则理解错误，对幂次矩阵本身进行元素非零的判断，而实际上是要对各次幂的和矩阵进行判断。3、warshall算法：warshall算法输出的并不是简单的图是否连通，而是一个判定矩阵。和邻接矩阵相比使用该矩阵判定图是否连通要容易很多，但还是需要一个判定过程。针对连通图warshall算法往往输出全一矩阵的规律，我的程序也是