中山大学数据科学与计算机学院-编译器构造实验报告-传递闭包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++代码作为实现示例。