3-图的连通性
《通信网理论基础》
实 验 指 导 书
适用专业—信息工程
实验三：图的连通性判断
一、实验目的
本次实验要求用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定连通分支的个数，使学生掌握Warshell 算法或矩阵幂算法的实现方法，培养算法设计与优化能力。
二、实验原理
1、Warshell 算法
Warshell 算法可解决图是否连通的问题, 而且效率很高。在该算法中，矩阵P 是判断矩阵，p ij =1表示从i 到j 连通，p ij =0表示从i 到j 不连通。
(1)置新矩阵 P:= C;
(2)置 i = 1;
(3)对所有的j , 如果p (j , i ) =1, 则对k=1,2,…,n
p (j , k ) :=p (j , k ) ∨p (i , k ) ;
(4) i =i +1;
(5) 如n ≥i 转向步骤(3), 否则停止。
2、矩阵幂算法
由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。可以通过对邻接阵C 做一些计算，得到图G 的一些性质。例如考虑C 3中的(i , j ) 的元素
(3) c i (, 3j ) ，如果它不为零，由于c i , j =∑∑c i , k c k , l c l , j ，则至少存在一组c i , k =c k , l =c l , j =1
k l
或一个长度为3的链使端i 和端j 相连。从而，通过计算C 的各阶幂次可得到关于图是否连通的信息。
3、算法分析
对于算法，基本问题是算法的正确性，其次是算法复杂度。从复杂度考虑，算法可以简单分为多项式复杂度和指数复杂度两大类，前者的目标是找到尽可能小的复杂度算法；后者的目标是找到合适的近似算法。
三、实验内容
(1) 两人一组，利用MATLAB 等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通分支数的判断。
(2) 比较Warshell 算法和矩阵幂算法在算法正确性和算法复杂度上的区别。
(3) 对算法进行优化。
四、实验报告
请提交电子版实验报告，内容包括但不限于以下方面：
实验内容；
所采取的实验方法：采用的语言，数据结构，主要的函数，算法的流程
图等；
实验结论与分析；
遇到的问题及解决方法：对算法或编程方面遇到的问题，查阅相关资料
或搜索电子资源，描述出现问题的原因以及解决的方案。
其他的有价值和意义的内容。
五、注意事项
✧ Deadline ：5月13号下午5点前
✧ 请将源代码以及实验报告打包，以“班级1+学号1+姓名1+班级2+学号2+
姓名2+实验三.rar ”的命名发送至[email protected]。
✧ 请在发送邮件的选项中选择“请求阅读回执”，不是在邮件正文中写这几个
字，那样的话需要我人工去回复。
✧ 杜绝抄袭，一旦发现，以0分论处。