计算机求解关系R的传递闭包

计算机求解关系R的传递闭包问题描述】用户输入关系R(程序设计者规定输入方式)，由计算机自动求解关系R的传递闭包。【设计背景】在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的nXn二值矩阵，则传递闭包的矩阵B+可如下计算:B+=B+B2+B3+ + (B)n式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为B,B(B),B(BB),B(BBB),……，所以在运算的每一步我们只需简单地把现有结果乘以B,完成矩阵的n次乘法即可。【算法优化】Warshall算法是求二元关系传递闭包的一种高效的算法。Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：置新矩阵A=M;置k=1;对所有i如果A[i,k]=l，则对j=l„n执行：A[i,j]-A[i,j]VA[k,j];k增1;如果kWn,则转到步骤(3),否则停止。所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。一.需求分析设定一个关系R(矩阵)，执行本程序，自动求出R的传递闭包。二．概要设计本程序采用的存储结构：二维数组包含的头文件：#include<stdio.h>定义的常量：defineN100inta[N][N],b[N][N],c[N][N];主程序的流程：{初始化同时置新数组；Warshall算法；输出传递闭包；}三．详细设计主函数的伪码算法：main(){//主程序for()for(){readcommand(cmd);//读入操作命令interpret(cmd); //解释执行操作命令}//数组初始化并置新；for()for(){readcommand(cmd);//读入操作命令interpret(cmd); //解释执行操作命令}//warshall算法；for()for(){readcommand(cmd);//读入操作命令interpret(cmd); //解释执行操作命令}//将非0元素变为1；for()for(){readcommand(cmd);//读入操作命令interpret(cmd); //解释执行操作命令}//输出传递闭包；调试分析1•本程序比较简单，仅有主函数，调试比较顺利。只有刚开始对warshall算法的中心思想不理解，后将逻辑算法改为C语言里的“+”后将非0元素全部改为1,程序得以程序运行。2.本程序的时间复杂度为0(N*N).五．使用说明1•运行本程序时，会提示输入矩阵的大小即n。2.页面提示输入矩阵，则输入设定的矩阵，数字之间用空格键隔开，输完一行按回车键换行，直到结束，页面自动出现所求的传递闭包。六．源程序#include<stdio.h>#include<iostream>#defineN100main(){intn,i,j,k;inta[N][N],b[N][N],c[N][N];printf("Pleaseinputn:");scanf("%d",&n);printf("Pleaseinputa[N][N]:\n");for(i=0;i<n;i++)for(j=0;j<n;j++){scanf("%d",&a[i][j]);b[i][j]=a[i][j];}for(k=0;k<n;k++)for(i=0;i<n;i++){if(a[i][k]==1){for(j=0;j<n;j++)c[i][j]=a[i][j]+a[k][j];for(i=0;i<n;i++)for(j=0;j<n;j++)if(c[i][j]!=0)c[i][j]=1;printf("Chuandibibaois:\n");for(i