请写一个c语言代码:根据Warshall算法的思想,编程实现求给定n个结点的图G的邻接矩阵A,得 到G的可达矩阵P。 输入说明:先输入图G的结点个数,然后依次输入图G的邻接矩阵A的每个元素。 输出说明:输出图G的可达矩阵d。
时间: 2024-03-07 22:49:29 浏览: 85
以下是一个C语言的代码实现:
```c
#include <stdio.h>
#define MAXN 100 // 定义最大结点数
void warshall(int n, int A[][MAXN], int P[][MAXN]) {
// 初始化P为A
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
P[i][j] = A[i][j];
}
}
// Warshall算法
for(int k=0; k<n; k++) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
P[i][j] = P[i][j] || (P[i][k] && P[k][j]);
}
}
}
}
int main() {
int n, A[MAXN][MAXN], P[MAXN][MAXN];
// 输入结点个数和邻接矩阵
scanf("%d", &n);
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf("%d", &A[i][j]);
}
}
// 求可达矩阵
warshall(n, A, P);
// 输出结果
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
printf("%d ", P[i][j]);
}
printf("\n");
}
return 0;
}
```
该程序使用Warshall算法求解可达矩阵。在函数`warshall`中,首先将可达矩阵P初始化为邻接矩阵A,然后使用三重循环依次更新P的每个元素。在主函数中,先输入结点个数和邻接矩阵A,然后调用`warshall`函数求解可达矩阵P,最后输出结果。
需要注意的是,该程序中定义了宏`#define MAXN 100`来表示最大结点数,如果结点数超过了这个值,程序可能会出现错误。
阅读全文