Warshall 算法的传递闭包实现
在计算机科学中，Warshall 算法是一种常用的图算法，用于计算图的传递闭包。传递闭包是指图中所有可能的路径的集合。 Warshall 算法的传递闭包可以用来解决许多实际问题，如计算二分图的最大匹配、计算图的-connected Components 等。
Warshall 算法的传递闭包的实现可以分为以下几个步骤：
1. 读取关系 R
我们需要读取关系 R，关系 R 是一个二元关系，表示图中的边。我们可以使用文件输入的方式来读取关系 R。
2. 初始化关系矩阵
接下来，我们需要将关系 R 转换为关系矩阵 mr[N][N]。关系矩阵是一个 N*N 的矩阵，其中 mr[i][j] 表示从节点 i 到节点 j 是否存在边。如果存在边，则 mr[i][j] 为 1，否则为 0。
3. 计算传递闭包
使用 Warshall 算法计算传递闭包。 Warshall 算法的基本思想是：对于每个节点 i，如果存在一条从节点 i 到节点 j 的路径，那么我们就可以从节点 i 到节点 k 的路径。 Warshall 算法的时间复杂度为 O(N^3)，其中 N 是图的节点数。
4. 输出传递闭包
我们可以输出传递闭包对应的关系矩阵。
下面是 Warshall 算法的传递闭包的 C++ 实现代码：
```c
#include <stdio.h>
#include <stdlib.h>
#define N 20
#define M 20
main() {
int i, j, k, m, n;
int r1[M], r2[M], a[N];
int mr[N][N] = {0};
FILE *fp;
printf("程序自动调用 c:/stone2.txt 文件内相应数据\n");
fp = fopen("c:\\stone2.txt", "r");
fscanf(fp, "%d", &n); /* 读取集合元素个数 */
for (i = 0; i < n; i++)
fscanf(fp, "%d", &a[i]); /* 读取集合元素 */
fscanf(fp, "%d", &m); /* 读取关系个数 */
for (k = 0; k < m; k++)
fscanf(fp, "%d, %d", &r1[k], &r2[k]); /* 读取关系 */
fclose(fp);
printf("自反闭包 r(R):\n{");
for (i = 0; i < n; i++)
printf("<%d, %d>, ", a[i], a[i]); /* 输出自反闭包 */
for (k = 0; k < m; k++) {
if (r1[k] != r2[k])
printf("<%d, %d>, ", r1[k], r2[k]);
else
continue;
}
printf("\b}\n");
printf("对称闭包 s(R):\n{");
for (k = 0; k < m; k++) {
if (r1[k] != r2[k])
printf("<%d, %d>, <%d, %d>, ", r1[k], r2[k], r2[k], r1[k]);
else
printf("<%d, %d>, ", r1[k], r2[k]);
}
printf("\b}\n");
k = 0;
for (i = 0; i < n, k < m; i++) {
if (r1[k] != a[i])
continue;
else {
for (j = 0; j < n, k < m; j++) {
if (r2[k] != a[j])
continue;
else {
mr[i][j] = 1;
k++;
i = 0;
j = 0;
break;
}
}
}
}
printf("关系所对应的关系矩阵:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%5d", mr[i][j]);
printf("\n");
}
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
mr[i][j] += mr[i][k] * mr[k][j];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
if (!mr[i][j])
continue;
else
mr[i][j] = 1;
}
printf("传递闭包对应关系矩阵:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%5d", mr[i][j]);
printf("\n");
}
system("PAUSE");
}
```
这段代码实现了 Warshall 算法的传递闭包，读取关系 R，计算关系矩阵，计算传递闭包，并输出传递闭包对应的关系矩阵。
