合肥工业大学2021离散数学上机实验四

合肥工业大学2021离散数学上机实验四 实验四：关系的闭包运算及 Floyd-Warshall 算法求解

1. 实验目的和要求

        实验目的：

        关系的闭包运算是对某一不满足某种特性的关系进行最“经济”（即增加尽可能少的序对）扩充的运算，使之具有某一特性。关系R的闭包运算主要包括 自反、对称和传递闭包，分别记为 r(R）、s(R)和t(R）。在熟悉计算原理的基础上，编程实现关系的三种性质闭包。

        实验要求：

        (1).利用关系矩阵求解有限集上给定关系的自反、对称和传递闭包。

        (2).自反和对称闭包的求解相对简单。自反闭包只要将关系矩阵的主对角线元素全部置1，对称闭包则是在求出当前关系矩阵的转置矩阵的基础上和原关系矩阵进行求和。

        (3).传递闭包的求解相对复杂，要求编码实现并验证 Warshall 算法。

        思路：自反和对称闭包的求解相对简单，传递闭包的求解相对复杂，沃舍尔算法是用来计算关系的传递闭包的一种高效率算法。这里推荐大家看沃舍尔算法的实现，方便理解。

      2. 实验环境和工具

        开发环境：Visual Studio 2019

      3. 实验结果

        3.1 程序流程图 

        3.2 程序代码 （仅供参考，水平有限，有错请指出）

#include
#include
using namespace std;
void Reflexive(int n, vector>a)
{
	//求自反闭包（主对角线全为1，a[n][n]=1） 
	cout << "===============================" << endl;
	cout << "自反闭包的关系矩阵：" << endl;
	for (int i=0; i < n; i++)
	{
		a[i][i] = 1;
		for (int j=0; j < n; j++)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	cout << "===============================" << endl;
}
void Symmetry(int n, vector>b)
{
	//求对称闭包（b[i][j]=1时，b[j][i]=1）
	int i = 0, j = 0;
	for (i=0; i < n; i++)
	{
		for (j=0; j < n; j++)
		{
			if (b[i][j] == 1)
			{
				b[j][i] = 1;
			}
		}
	}
	cout << "对称闭包的关系矩阵：" << endl;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			cout << b[i][j] << " ";
		}
		cout << endl;
	}
	cout << "===============================" << endl;
}
void Transfer(int n, vector>c)
{
	//求传递闭包（Floyd-Warshall算法）
	int k, i = 0, j = 0;
	for (i=0; i < n; i++)
	{
		for (j=0; j < n; j++)
		{
			if (c[j][i] == 1)
			{
				for (k = 0; k < n; k++)
				{
					c[j][k] = c[j][k] + c[i][k];					
					if (c[j][k] > 1)//将关系矩阵中大于1的值改为1 
						c[j][k] = 1;
				}
			}
		}
	}
	cout << "传递闭包的关系矩阵：" << endl;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			cout << c[i][j] << " ";
		}
		cout << endl;
	}
}
int main() 
{
	int i, j, n;
f:	cout << "请输入关系矩阵的阶数n:" << endl;
	cin >> n;
	vectorv(n);
	vector>a(n,v), b(n,v), c(n,v);
	cout << "请依次输入关系矩阵的真值（0或1）：" << endl;
	for (i = 0; i < n; i++) 
	{
		for (j = 0; j < n; j++) 
		{
			cin >> a[i][j];//自反闭包关系矩阵
			if (a[i][j] != 0 && a[i][j] != 1) 
			{
				cout << "输入错误！" << endl;
				goto f;
			}
			b[i][j] = a[i][j]; //对称闭包关系矩阵
			c[i][j] = a[i][j]; //传递闭包关系矩阵 
		}
	}
	//求自反闭包（主对角线全为1，a[n][n]=1） 
	Reflexive(n, a);
	//求对称闭包（b[i][j]=1时，b[j][i]=1）
	Symmetry(n, b);
	//求传递闭包（Floyd-Warshall算法）
	Transfer(n, c);
	return 0;
}

        3.3 运行结果

​

其他作业：

合肥工业大学2021离散数学上机实验一https://blog.csdn.net/qq_52791068/article/details/122654230合肥工业大学2021离散数学上机实验六https://blog.csdn.net/qq_52791068/article/details/122656801

合肥工业大学2021离散数学上机实验八https://mp.csdn.net/mp_blog/creation/editor/122663212