输入一个集合的二元关系,判定其是否满足自反性、反自反性、对称性、反对称性、传递性。并求出自反、对称和传递闭包。
大二上学期时的写的代码,C++语言实现。
#include<iostream>
#include<string>
using namespace std;
class Relation//构造函数
{
private:
int R[11][2];//存储关系R
int R1[11][2], R2[11][2], R3[11][2];//分别存储自反,对称,传递闭包
int m,n;//分别存储二元关系R中的最大值和最小值
int o;//存储二元关系个数
int M[10][10];//存储转换后的矩阵
public:
Relation()//构造函数
{
n = 10;
m = -1;
o = PutInR();
memset(M,0,sizeof(M));
}
int PutInR();//输入关系R
void Convent();//转换为矩阵
void Give();//用R初始化R1,R2
bool Reflex();//判断自反性
bool UnReflex();//判断反自反性
bool Symme();//判断对称性
bool AnSymme();//判断反对称性
bool Delivery();//判断传递性
void Decide();//性质判定
void ReflexB();//求自反闭包
void SymmeB();//求对称闭包
void DeliveryB();//求传递闭包
};
//输入关系R -- 以‘-1’结尾
int Relation::PutInR()
{
int i = 0, k = 0, l = 0;
cout << "请输入关系R: "<<endl;
for (i; i <= 10; i++)
{
cin >> R[i][0];
cin >> R[i][1];
if (R[i][1] == -1)break;//结束标志为-1
l = R[i][0] > R[i][1] ? R[i][0] : R[i][1];
k = R[i][0] < R[i][1] ? R[i][0] : R[i][1];
m = m > l ? m : l;
n = n > k ? k : n;
}
return i;
}
//转换为矩阵
void Relation::Convent()
{
int i = 0;
while (R[i][0] != -1)
{
M[R[i][0]][R[i][1]] = 1;//相应矩阵位置赋1
i++;
}
}
//判断自反性
bool Relation::Reflex()
{
for (int i = n; i <= m;i++)
{
if (M[i][i] == 0)return false;//对角线上有元素为0,则不满足
}
cout << "具有自反性" << endl;
return true;
}
//判断反自反性
bool Relation::UnReflex()
{
for (int i = n; i <= m; i++)
{
if (M[i][i] == 1)return false;//对角线上有元素为1,则不满足
}
cout << "具有反自反性" << endl;
return true;
}
//判断对称性
bool Relation::Symme()
{
for (int i = n; i <= m; i++)
{
for (int j = i; j <= m; j++)
{
if (M[i][j] == 1 && M[j][i] != 1)return false;//不关与对角线对称,则不满足
}
}
cout << "具有对称性" << endl;
return true;
}
//判断反对称性
bool Relation::AnSymme()
{
for (int i = n; i <= m; i++)
{
for (int j = n; j <= m; j++)
{
if (M[i][j] == 1 && M[j][i] == 1)return false;//关于对角线对称,则不满足
if (M[i][j] == 0 && M[j][i] == 0)return false;
}
}
cout << "具有反对称性" << endl;
return true;
}
//判断传递性
bool Relation::Delivery()
{
int k[10] = { 0 }, l[10] = { 0 };
for (int i = n; i <= m; i++)//以对角线上每个元素循环
{
int e = 0, f = 0;
for (int j = n; j <= m; j++)
{
if (M[i][j] == 1 && i != j) { k[e++] = j; }//找出第i行的非0元素,列下标记录在a数组中
if (M[j][i] == 1 && i != j) { l[f++] = j; }//找出第i列的非0元素,行下标记录在b数组中
}
for (int c = k[0]; c <= k[--e]; c++)//行上的非0元素
{
for (int d = l[0]; d <= k[--f]; d++)//列上的非0元素
{
if (M[i][c] == 1 && M[d][i] != 1|| M[i][c] != 1 && M[d][i] == 1)return false;
}
}
}
cout << "具有传递性" << endl;
return true;
}
//性质判定
void Relation::Decide()
{
Convent();
Reflex();
UnReflex();
Symme();
AnSymme();
Delivery();
}
//用R初始化R1,R2
void Relation::Give()
{
memcpy(R1, R, 22);
memcpy(R1, R, 22);
}
//求自反闭包
void Relation::ReflexB()
{
int g = o;
for (int i = n; i <= m ; i++)
{
if (M[i][i] == 0)//如果缺少对角线上的元素
{
//连接在R1后面
R1[g][0] = i;
R1[g][1] = i;
g++;
}
}
cout << "自反闭包是:" << endl;
for (int j = 0; j < g ; j++)
{
cout <<'<'<<R1[j][0]<<','<<R1[j][1]<<'>';
}
cout << endl;
}
//求对称闭包
void Relation::SymmeB()
{
int g = o;
for (int i = n; i <= m; i++)
{
for (int j = i; j <= m; j++)
{
if (M[i][j] == 1 && M[j][i] != 1)//如果不关于对角线对称
{
R2[g][0] = j;//相对应的元素连接在R2后面
R2[g][1] = i;
g++;
}
if (M[i][j] != 1 && M[j][i] == 1)//如果不关于对角线对称
{
R2[g][0] = j;//相对应的元素连接在R2后面
R2[g][1] = i;
g++;
}
}
}
cout << "对称闭包是:" << endl;
for (int j = 0; j < g ; j++)
{
cout << '<' << R2[j][0] << ',' << R2[j][1] << '>';
}
cout << endl;
}
//求传递闭包
void Relation::DeliveryB()
{
int g = 0;
for (int t = n; t <= m ; t++)
{
for (int j = n; j <= m; j++)
{
if (M[t][j] == 1)
{
for (int k = n; k <= m; k++)
{
M[j][k] = M[t][k] || M[j][k];//Warshall算法求解传递闭包
}
}
}
}
for (int i = n; i <= m; i++)//将矩阵反转回二元数组
{
for (int j = n; j <= m; j++)
{
if (M[i][j] == 1)
{
R3[g][0] = i;
R3[g][1] = j;
g++;
}
}
}
cout << "传递闭包是:" << endl;
for (int j = 0; j < g-1; j++)
{
cout << '<' << R3[j][0] << ',' << R3[j][1] << '>';
}
cout << endl;
}
int main()
{
Relation real;
real.Decide();
real.Give();
real.ReflexB();
real.SymmeB();
real.DeliveryB();
return 0;
}