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

离散数学实验训练学 院 计算机与信息技术学院 指导老师 景丽萍 学生姓名 谢昂 学 号 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,jAi,jAk,j;（4）k增1;（5）如果kn，则转到步骤（3），否则停止。所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。三、需求分析用户要自己计算出二元关系的矩阵形式，输入时要按矩阵输入，从第一排第一个开始输入，直到第一排全部输入（每两个数字之间要输入一个空格），然后按回车转换到下一行，以同样的形式输入该行数字，全部输入完成后按回车。然后会输出一个矩阵就是所求的关系R的传递闭包矩阵。程序可以求任意关系R的传递闭包，但必须按要求输入正确的关系矩阵形式。四、概要设计在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的nn二值矩阵，则传递闭包的矩阵B*可如下计算：B*=B+B2+B3+(B)n式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为B，B(B)，B(BB)，B(BBB)，所以在运算的每一步我们只需简单地把现有结果乘以B，完成矩阵的n次乘法即可。五、主要实验流程图程序开始输入矩阵的维数输入矩阵各元素的值输入是否正确?计算出可传递闭包关系矩阵打印可传递闭包的关系矩阵结束正确不正确六、实验源代码#include stdio.hvoid Warshall(int n)int i , j, k;int temp100100;int is_correct=0;flag:while(is_correct=0)fflush(stdin);for(int a=0;an;a+)printf(请输入矩阵第%d行元素:,a+1);for(int b=0;bn;b+)scanf(%d,&tempab);if(tempab=0|tempab=1) /判断输入是否合法is_correct=1;elseis_correct=0;printf(矩阵输入错误！请重新输入n);goto flag;for(i=0;in;i+)for(j=0;jn;j+)if(tempji=1)for(k=0;kn;k+)tempjk=tempik|tempjk;printf(传递闭包关系矩阵t(R):n);for(i=0;in;i+) for(j=0;jn;j+)printf(%dt, tempij);printf(n);int main(int argc, char* argv)int n;printf(请输入关系矩阵的维数: );scanf(%d,&n);Warshall(n);return 0;七、试验结果截图展示八、实验总结Warsh