中山大学数据科学与计算机学院-编译器构造实验报告-传递闭包Warshall算法
"中山大学数据科学与计算机学院本科生实验报告 - 编译器构造实验" 实验报告的主题是关于传递闭包的Warshall算法,这是一种在图论和计算机科学中用于计算关系传递闭包的算法。传递闭包是指在一个关系集合中,通过一系列的传递关系,将所有可能连接起来的元素对包含进去的新关系。这里的"关系"通常表示为一个矩阵,其中1表示存在某种关系,0表示不存在。 Warshall算法的基本思想是迭代地更新一个矩阵,该矩阵代表了原始关系。算法的伪代码如下: 1. 初始化新矩阵A等于原始关系矩阵M。 2. 设置计数器k为1。 3. 对于每个元素i,如果A[i, k]为1(即存在关系i到k),则对所有元素j执行: - 增加k的值。 - 如果k小于或等于n(矩阵的行数或列数),则回到步骤3,否则结束循环。 4. 得到的矩阵A即为关系R的传递闭包t(R)。 给出的C++程序实现了这个算法,首先读取矩阵的行数和关系矩阵M,然后通过三层嵌套循环来执行Warshall算法。程序首先遍历矩阵的每一行,检查是否存在i到j的关系,如果存在,再检查是否存在i到k的关系,如果两者都存在,那么就设置j到k的关系为1。最后,程序输出计算得到的传递闭包矩阵。 测试数据包括一组5x5的关系矩阵,其初始形式为: ``` 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 ``` 经过Warshall算法处理后,会得到传递闭包矩阵,显示了所有可能通过一次或多次传递得到的关系。 此实验报告属于2018-2019学年的第二学期,16级计算机科学与技术专业学生的作业,由学号16337341的朱志儒同学完成。实验在2019年4月26日进行并完成。 总结来说,这个实验涉及了图论中的传递闭包概念,具体实现是通过Warshall算法,该算法能够有效地计算出一个关系矩阵的传递闭包,并且提供了C++代码作为实现示例。
![](https://csdnimg.cn/release/download_crawler_static/86390261/bg1.jpg)
下载后可阅读完整内容,剩余3页未读,立即下载
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/3be06f59ba094c62afbf0b9c6e85c290_weixin_35779370.jpg!1)
- 粉丝: 25
- 资源: 314
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决Eclipse配置与导入Java工程常见问题
- 真空发生器:工作原理与抽吸性能分析
- 爱立信RBS6201开站流程详解
- 电脑开机声音解析:故障诊断指南
- JAVA实现贪吃蛇游戏
- 模糊神经网络实现与自学习能力探索
- PID型模糊神经网络控制器设计与学习算法
- 模糊神经网络在自适应PID控制器中的应用
- C++实现的学生成绩管理系统设计
- 802.1D STP 实现与优化:二层交换机中的生成树协议
- 解决Windows无法完成SD卡格式化的九种方法
- 软件测试方法:Beta与Alpha测试详解
- 软件测试周期详解:从需求分析到维护测试
- CMMI模型详解:软件企业能力提升的关键
- 移动Web开发框架选择:jQueryMobile、jQTouch、SenchaTouch对比
- Java程序设计试题与复习指南
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)