计算机求解关系R的传递闭包
- 格式：doc
- 大小：54.50 KB
- 文档页数：4
计算机求解关系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次乘法即可。
【算法优化】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的传递闭包。
二．概要设计
1.本程序采用的存储结构：二维数组
2.包含的头文件：#include<stdio.h>
3.定义的常量：define N 100
int a[N][N],b[N][N],c[N][N];
4.主程序的流程：
{
初始化同时置新数组；
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.本程序的时间复杂度为O(N*N).
五．使用说明
1.运行本程序时，会提示输入矩阵的大小即n。
2.页面提示输入矩阵，则输入设定的矩阵，数字之间用空格键隔开，输完一行按回车键换行，直到结束，页面自动出现所求的传递闭包。
六．源程序
#include<stdio.h>
#include<iostream>
#define N 100
main()
{
int n,i,j,k;
int a[N][N],b[N][N],c[N][N];
printf("Please input n:");
scanf("%d",&n);
printf("Please input a[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("Chuandi bibao is:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d ",c[i][j]);
printf("\n");
}
system("pause");
}七．测试结果。
