离散数学实验 C 关系的运算 幂运算 闭包运算

实验2关系的运算 （1） 关系的幂运算

输入：集合A，二元关系集合R，幂次n 输出：R的n次幂

要求：尽量使运算的计算量最小 （2） 关系闭包的计算 输入：集合A，二元关系集合R 输出：R的传递闭包t(R) 要求：

(a) 采用Warshall算法（89页） (b) 编写代码判断输出t(R)为传递闭包 程序代码:

#include #include #include usingnamespacestd;

typedefvector>Mat; classRelation{ vectors;//集合 MatA;//关系矩阵 MatB;

MatC; MatE;

MatD[100];//用来存储矩阵 intn; public:

voidinputs();//将集合存入向量中

voidinputa();//将读入的关系转化为关系矩阵 voidprint();//输出关系矩阵 voidmi(); intWarshall(); };//定义类

intn,m;//全局变量，下文中使用 voidRelation::inputs(){ cout<<\输入集合\ for(inta;cin>>a;){ s.push_back(a); if(getchar()=='\\n') break;}

}//将集合存入向量中

voidRelation::inputa(){//将读入的关系转化为关系矩阵 cout<<\输入关系\ inti,j,e,r;

for(i=0;iu; for(j=0;j

u.push_back(ia);} A.push_back(u); B.push_back(u); C.push_back(u); E.push_back(u);

}//创建二维向量，初始化，是每个元素为0 for(inth,z;cin>>h>>z;){ if(h==0&&z==0) break;

for(i=0;i

A[e][r]=1;B[e][r]=1;

E[e][r]=1;//C[e][r]=1;//读入关系，将关系对应的矩阵中的位置元素变为1 if(getchar()=='\\n') break;

} }

voidRelation::print(){ for(inti=0;i

}//输出关系矩阵 voidRelation::mi(){ inta,b,i,c; cin>>n;//读入幂次 if(n==0){//0次幂

for(intk=0;k

cout<<\对角线上元素为1 else

cout<<\ }

cout<

} else{

for(i=1;i

for(inth=0;h

for(intx=0;x

m=m+B[h][x]*A[x][d];//第h行第d列的元素对应相乘的和 }

C[h][d]=m; } } if(i>1){

for(a=0;a

if(b!=s.size())break; }

}//检验是否重复