利用Warshall算法求二元关系的可传递闭包

1、利用Warshall算法求二元关系 的可传递闭包离散数学实验训练学 院计算机与信息技术学院指导老师景丽萍学生姓名_ 谢昂学 号 13281164提交日期2014年5月22日利用Warshall算法求二元关系的可传递闭包学生：谢昂指导老师：景丽萍一、设计方案简介设计一个程序实现求解关系R的传递闭包二、Warshall 算法Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M（1）置新矩阵A=M;（2）置 k=1;（3）对所有i如果Ai,k=1 ，则对j=1.n执行：Ai,j Ai,j V(4) k 增 1;(5) 如果k&l

2、t;n,则转到步骤(3),否则停止。所得的矩阵 A 即为关系R的传递闭包t(R)的关系矩阵。三、需求分析用户要自己计算出二元关系的矩阵形式，输入时要按矩阵输入， 从第一排第一个开始输入，直到第一排全部输入(每两个数字之间要 输入一个空格)，然后按回车转换到下一行，以同样的形式输入该行 数字，全部输入完成后按回车。然后会输出一个矩阵就是所求的关系 R的传递闭包矩阵。程序可以求任意关系 R的传递闭包，但必须按要 求输入正确的关系矩阵形式。四、概要设计在集合X上的二元关系R的传递闭包是包含R的X上的最小的传 递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通 性描述等方面都是基本概念。一般

3、用B表示定义在具有n个元素的集 合X上关系R的nXn二值矩阵，则传递闭包的矩阵B*可如下计算：B* = B + B2 + B3 +(B) n式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为 B, B(B), B(BB), B(BBB),，所以 在运算的每一步我们只需简单地把现有结果乘以B,完成矩阵的n次乘法即可。五、主要实验流程图六、实验源代码#i nclude "stdio.h"void Warshall(i nt n)int i , j, k;int temp100100;int is_correct=0;flag:while(is_co

4、rrect=0) _fflush(stdi n);for(i nt a=0;a <n; a+)printf(" 请输入矩阵第c行元素:",a+1);for(i nt b=0;b <n ;b+)scan f("%d", &tempab);if(tempab=0|tempab=1)/判断输入是否合法is_correct=1;elseis_correct=0;printf(”矩阵输入错误！请重新输入n");goto flag;for(i=0;i< n;i+)for(j=0;j< n;j+)if(tempji=1)for

5、(k=0;k< n; k+)tempjk=tempik|tempjk;printf("传递闭包关系矩阵t(R):n");for(i=0;i <n ;i+)for(j=0;j <n ;j+)printf("%dt", tempij); prin tf("n");int main (i nt argc, char* argv)int n;printf("请输入关系矩阵的维数：");sca nf("%d",&n);Warshall( n);return 0;七、试验结果截图展示L:usersA am inistratorL?e sictop 永门 八、实验总结阵1 2 賈霖第第系 系无 入人人人人闭-. 1 _ as - - l-,<_"lul-. F 0Haa 1-1丄丄丄4!£n土冃主冃主冃主冃土冃±v墾兀兀兀一004 0:11 00 1: - - V/11Press11key11 t