等价关系的判定 C++实现

一、自反性判断

//自反性判断
bool isZifan(int *M[],int n) {   //检查对角线元素是否为1
	for(int i=0;i 
二、对称性判断
 
//对称性判断
bool isDuichen(int *M[],int n) {  //检查是否关于对角线对称
	for(int i=0;i 
三、传递性判断
 
方法1：Floyd-Warshall算法（矩阵乘法）
 
思路：设M是R的关系矩阵，若M*M为M的子集，则R具有传递性。
 
判断方法：计算M*M，M*M为M的子集的意思是，在方阵对应的同行同列的位置，若对于M，该数为0，则对于M*M，该数必为零，否则R不具有传递性。即：若M中的a[i][j] == 0, 则必有M*M中的c[i][j] == 0 。
 
bool isChuandi(int *M[],int n) {
	int **tmp=NULL;
	tmp=new int* [n];
	for(int i=0;i 
方法2：基于图论的dfs寻路（中途点判别法）
 
思路：利用矩阵表示方法，遍历这个矩阵如果遇到一个等于1的位置，记录位置，利用其纵坐标作为下一个数的横坐标，在此横坐标下找到是1的位置，记录这个位置，在利用上一个数位置的横坐标和这个数的纵坐标找到一个新的位置，如果这个位置上是1，那么这个数就具有可传递性，然后继续遍历进行这个循环操作，知道检查到所有的数都对上了，这个二元关系才可说具有可传递性，有一个不符的则不是具有传递性的二元关系。
 
bool isChuandi(int *M[],int n) {
	bool flag=1;     //假定具有传递性
	for(int i=0;i 
四、主函数
 
int main() {
	int **M=NULL;
	int n;
	cout<<"请输入二元关系对应方阵（n*n）的行数："<>n;
	M=new int* [n];
	for(int i=0;i>M[i][j];
		}
	}
	if(isZifan(M,n) && isDuichen(M,n) && isChuandi(M,n)) { //判断是否为等价关系
		cout<<"该二元关系是等价关系！"<