Warshall算法:设R是n个元素集合上的二元关系,M是R的关系矩阵; (1) 置新矩阵A:=M (2) 置i:=1; (3) for j=1 to n do if A[j,i]=1 then do for k=1 to n do A[j,k]:=A[j,k]+A[i,k] (4) i=i+1; (5) if i<=n then to (3) else stop 本实验要求从键盘输入一个关系的关系矩阵,计算其自反闭包、对称闭包和传递闭包,计算传递闭包时使用Warshall算法。用C语言或MATLAB实现。 实验源代码
时间: 2024-03-06 09:47:31 浏览: 67
Warshall算法求传递闭包Python实现
5星 · 资源好评率100%
以下是使用C语言实现Warshall算法求解自反闭包、对称闭包和传递闭包的代码:
```
#include <stdio.h>
#define MAX_SIZE 100
int main()
{
int n, i, j, k;
int R[MAX_SIZE][MAX_SIZE], A[MAX_SIZE][MAX_SIZE];
printf("请输入矩阵的大小n:");
scanf("%d", &n);
printf("请输入关系矩阵R:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &R[i][j]);
}
}
// 计算自反闭包
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (i == j) {
A[i][j] = 1;
} else {
A[i][j] = R[i][j];
}
}
}
printf("自反闭包:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", A[i][j]);
}
printf("\n");
}
// 计算对称闭包
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (R[i][j] == 1 && R[j][i] == 0) {
A[j][i] = 1;
}
}
}
printf("对称闭包:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", A[i][j]);
}
printf("\n");
}
// 计算传递闭包
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
A[i][j] = R[i][j];
}
}
for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
A[i][j] = A[i][j] || (A[i][k] && A[k][j]);
}
}
}
printf("传递闭包:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", A[i][j]);
}
printf("\n");
}
return 0;
}
```
输入关系矩阵后,依次输出自反闭包、对称闭包和传递闭包的结果。
阅读全文