电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

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

利用Warshall算法求二元关系的可传递闭包_第1页
1/7
利用Warshall算法求二元关系的可传递闭包_第2页
2/7
利用Warshall算法求二元关系的可传递闭包_第3页
3/7
离散数学实验训练学院计算机与信息技术学院指导老师景丽萍学生姓名谢昂学号13281164提交日期2014年5月22日利用Warshall算法求二元关系的可传递闭包学生:谢昂指导老师:景丽萍一、设计方案简介设计一个程序实现求解关系R的传递闭包二、Warshall算法Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下,设在n个元素的有限集上关系R的关系矩阵为M:(1)置新矩阵A=M;(2)置k=1;(3)对所有i如果A[i,k]=1,则对j=1..n执行:A[i,j]←A[i,j]∨A[k,j];(4)k增1;(5)如果k≤n,则转到步骤(3),否则停止。所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。三、需求分析用户要自己计算出二元关系的矩阵形式,输入时要按矩阵输入,从第一排第一个开始输入,直到第一排全部输入(每两个数字之间要输入一个空格),然后按回车转换到下一行,以同样的形式输入该行数字,全部输入完成后按回车。然后会输出一个矩阵就是所求的关系R的传递闭包矩阵。程序可以求任意关系R的传递闭包,但必须按要求输入正确的关系矩阵形式。四、概要设计在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的n×n二值矩阵,则传递闭包的矩阵B*可如下计算:B*=B+B2+B3+……+(B)n式中矩阵运算时所有乘法都用逻辑与代替,所有加法都用逻辑或代替。上式中的操作次序为B,B(B),B(BB),B(BBB),……,所以在运算的每一步我们只需简单地把现有结果乘以B,完成矩阵的n次乘法即可。五、主要实验流程图程序开始输入矩阵的维数输入矩阵各元素的值输入是否正确?计算出可传递闭包关系矩阵打印可传递闭包的关系矩阵结束正确不正确六、实验源代码#include"stdio.h"voidWarshall(intn){inti,j,k;inttemp[100][100];intis_correct=0;flag:while(is_correct==0){fflush(stdin);for(inta=0;a

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

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

确认删除?
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群