(word完整版)图的连通性判断matlab实验报告.doc
需积分: 9 80 浏览量
2022-10-24
01:59:39
上传
评论
收藏 505KB DOC 举报
(word 完整版)图的连通性判断 matlab 实验报告
实验三:图的连通性判断
一、实验目的
用计算机语言编写图的连通性判断算法，可输入图的邻接矩阵，判断图是否连通以及确定
连通分支的个数,掌握 Warshell 算法或矩阵幂算法的实现方法。
二、实验原理
1、Warshell 算法
Warshell 算法可解决图是否连通的问题， 而且效率很高.在该算法中，矩阵
P
是判断矩阵，
1�
ij
p
表示从
i
到
j
连通，
0�
ij
p
表示从
i
到
j
不连通.
(1）置新矩阵
P:= C
;
(2）置
i
= 1
;
（3)对所有的
j
，若
1),( �ijp
，
则对
k=1，2，…,n
, 有
),(),(:),( kipkjpkjp ��
;
(4）
1�� ii
；
（5) 如
in �
转向步骤（3)， 否则停止。
2、矩阵幂算法
由于邻接阵包含了图的所有信息，和关联阵一样，是图的等价表示。可以通过对邻接阵 C
做一些计算，得到图 G 的一些性质。例如考虑
3
C
中的
),( ji
的元素
)3(
, ji
c
，如果它不为零，由于
� �
�
k
jllkkiji
cccc
l
,,,
)3(
,
，则至少存在一组
1
,,,
���
jllkki
ccc
或一个长度为 3 的链使端
i
和端
j
相连。从
而，通过计算 C 的各阶幂次可得到关于图是否连通的信息。
三、实验内容
1。利用 MATLAB 等语言实现图的连通性判断算法，可对输入的邻接阵进行连通性以及连通分支
数的判断.
2.比较 Warshell 算法和矩阵幂算法在算法正确性和算法复杂度上的区别。
资源评论
智慧安全方案
- 粉丝: 3613
- 资源: 59万+
最新资源
- 嵌入式基础学习资料0000
- content_1714465331721.xls
- HM3401-VB一款P-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- Chainbase+Web3+APi+Data warehouse
- HM3401D-VB一款P-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- GEE案例-1990-2023年计算某个区域的NDVI时序变化轨迹（以徐州市为例）含全部代码.pdf
- HM3401C-VB一款P-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- 沈丘盛世龙门图纸符合规范化
- 基于51单片机带LCD1602显示+温度补偿的超声波测距仪设计软硬设计+仿真+文档资料.zip
- 一、K210是什么？ K210全称为堪智K210,是嘉楠科技自主研发的一款采用RISC-V处理器架构，具备视听一体、自主IP内核
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
