c语言warshall算法求传递闭包

### 回答1：
Warshall算法是一种求解传递闭包的算法，其基本思想是利用矩阵乘法的性质，通过多次迭代来逐步构建传递闭包。

具体实现过程如下：

1. 初始化传递闭包矩阵，即将原始矩阵复制到传递闭包矩阵中。

2. 对传递闭包矩阵进行多次迭代，每次迭代都将传递闭包矩阵中的每个元素与其所在行和列的所有元素进行逻辑“或”操作，得到新的传递闭包矩阵。

3. 当传递闭包矩阵不再发生变化时，迭代结束，此时得到的传递闭包矩阵即为原始矩阵的传递闭包。

需要注意的是，传递闭包矩阵的元素类型应为布尔型，表示两个节点之间是否存在路径。

在C语言中，可以使用二维数组来表示矩阵，使用循环嵌套来进行迭代操作，具体实现代码如下：

void warshall(int n, int graph[][n]) {
int i, j, k;
for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
}
}
}
}

其中，n表示矩阵的大小，graph为传递闭包矩阵，使用“||”表示逻辑“或”操作，使用“&&”表示逻辑“与”操作。

调用该函数即可求解传递闭包，传递闭包矩阵中的元素为1表示两个节点之间存在路径，为0表示不存在路径。

### 回答2：
Warshall算法是经典的求解传递闭包的算法，它是一种基于动态规划的算法。在C语言中，实现Warshall算法需要实现以下几个步骤：

Step1：定义矩阵

首先，我们需要定义一个n*n的矩阵来存储图的连接矩阵（邻接矩阵）。

#define N 100

int graph[N][N]; //存储连接矩阵

Step2：初始化图

根据需求，我们需要初始化图，使得所有的边都被标记为false。

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
graph[i][j]=false;
}
}

Step3：构建连接矩阵

接下来，我们需要根据输入的边信息，构建连接矩阵。

for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
graph[u][v]=true;
}

Step4：求解传递闭包

最后，我们需要使用Warshall算法求解传递闭包。

for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
graph[i][j]|=graph[i][k]&graph[k][j];
}
}
}

以上代码中，k表示中间点，i和j分别表示起点和终点。最终得到的graph即为传递闭包。

总结

通过以上四个步骤，我们可以实现Warshall算法来求解传递闭包。Warshall算法的时间复杂度为O(n^3)，在大多数情况下是足够快的。而且，由于其动态规划的思想，可以避免重复计算，提高了运行效率。

### 回答3：
Warshall算法是用来求解传递闭包的一种经典算法，它是基于矩阵乘法的思想，通过对一个矩阵不断地进行运算，最终得到该关系的传递闭包。在C语言中实现Warshall算法的过程如下：

1. 定义两个二维数组M和T，用来存储原始的关系矩阵和传递闭包矩阵。其中，M[i][j]表示从i到j是否存在一条边，T[i][j]表示从i到j是否存在一条路径。

2. 根据输入的边的信息，初始化矩阵M。例如，如果输入的边为(1,2)，则M[1][2]赋值为1，表示从1到2存在一条边。

3. 对矩阵T进行初始化，将其赋值为矩阵M。

4. 利用Warshall算法不断更新矩阵T，直到得到传递闭包矩阵为止。具体的更新过程如下：

for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
T[i][j] = T[i][j] || (T[i][k] && T[k][j]);
}
}
}

5. 输出传递闭包矩阵T，其中T[i][j]为1表示从i到j存在一条路径，为0表示不存在。

总的来说，Warshall算法是一种高效的算法，它的时间复杂度为O(n^3)，适用于较大规模的关系矩阵。在实际应用中，它常被用来处理网络中的路由问题，或者在数据库中优化查询语句。