warshall算法求传递闭包

Warshall算法是一种求解传递闭包的经典算法，其基本思想是利用矩阵乘法的性质来实现传递闭包的计算。

以下是使用C语言实现Warshall算法求解传递闭包的示例代码：

#include <stdio.h>

#define MAXN 100

int n; // 图的节点数
int g[MAXN][MAXN]; // 图的邻接矩阵
int c[MAXN][MAXN]; // 传递闭包的邻接矩阵

void warshall() {
    int i, j, k;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            c[i][j] = g[i][j]; // 初始化传递闭包矩阵
        }
    }
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                c[i][j] = c[i][j] || (c[i][k] && c[k][j]); // 利用矩阵乘法的性质更新传递闭包矩阵
            }
        }
    }
}

int main() {
    int i, j;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &g[i][j]); // 输入图的邻接矩阵
        }
    }
    warshall(); // 求解传递闭包
    printf("传递闭包矩阵：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", c[i][j]); // 输出传递闭包矩阵
        }
        printf("\n");
    }
    return 0;
}