求对称闭包给定有限集合上二元关系的关系矩阵,求其对称闭包的关系矩阵第一行输入矩阵维数n(n<=100) 第二行至第n+1行输入关系矩阵 输出对称闭包的关系矩阵c语言实现dev-c++5.11实现
时间: 2023-12-03 20:45:14 浏览: 49
下面是对称闭包的 C 代码实现:
```c
#include <stdio.h>
#define MAX_SIZE 100
int main() {
int n, i, j, k;
int matrix[MAX_SIZE][MAX_SIZE], closure[MAX_SIZE][MAX_SIZE];
// 读入矩阵维数和关系矩阵
scanf("%d", &n);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &matrix[i][j]);
closure[i][j] = matrix[i][j]; // 初始化闭包矩阵
}
}
// 对称闭包算法
for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (closure[i][k] && closure[k][j]) {
closure[i][j] = 1;
}
}
}
}
// 输出对称闭包矩阵
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", closure[i][j]);
}
printf("\n");
}
return 0;
}
```
其中,`matrix` 数组存放原始关系矩阵,`closure` 数组存放对称闭包矩阵。算法使用三重循环,依次遍历所有可能的路径,如果路径两端都有关系,则认为它们之间也有关系。
需要注意的是,算法的时间复杂度为 $O(n^3)$,因此当矩阵维数较大时,运行时间会很长。