c++ warshall算法求传递闭包

Warshall算法可以求解有向图的传递闭包，其基本思想是利用动态规划的思想，通过计算图中任意两个节点之间是否存在一条路径，来得到整个图的传递闭包。

具体的算法步骤如下：

1. 初始化传递闭包矩阵R为原有的邻接矩阵W。

2. 对于每一个节点i，遍历邻接矩阵R的第i行，如果存在一个节点j，使得R[i][j]=1，那么对于邻接矩阵W的第j行中的所有元素k，令R[i][k]=1。

3. 重复步骤2，直到邻接矩阵R不再发生变化为止。

最终得到的R即为原有有向图的传递闭包。

需要注意的是，Warshall算法只适用于有向图，对于无向图需要先将其转化为有向图才能使用。同时，该算法时间复杂度为O(n^3)，对于大规模的图可能会存在性能问题。

相关问题

warshall算法求传递闭包c++

### 回答1：
Warshall算法是一种求解传递闭包的经典算法，其基本思想是利用矩阵乘法的性质，通过多次迭代来计算出传递闭包。具体实现过程如下：

1. 定义一个二维数组trans，用于存储传递闭包的结果，初始化为邻接矩阵。

2. 对于每一个中间节点k，遍历所有的节点i和j，如果存在一条从i到j的路径经过k，则将trans[i][j]设为1。

3. 重复执行步骤2，直到所有的中间节点都被遍历过为止。

4. 最终得到的trans就是原图的传递闭包。

以下是C++代码实现：

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

其中，n表示节点数，graph是邻接矩阵。函数执行完毕后，graph中存储的就是传递闭包。

### 回答2：
Warshall算法是一种用于计算有向图的传递闭包的算法。该算法是以其发明者Floyd Warshall的名字命名的。

传递闭包表示所有可以从i到j到达的点对(i,j)。如果在图中有一条从i到j的路径，那么(i,j)就在传递闭包中。

Warshall算法使用二阶矩阵递推的方法进行计算。算法一开始会读入输入的图形，例如一个n x n的邻接矩阵A。接下来，算法会根据输入的图形逐步计算出所有的传递闭包中的点对。

算法的核心在于使用一个二阶矩阵B作为过渡矩阵。该矩阵最初等于邻接矩阵A。之后，算法会迭代修改过渡矩阵B中的元素，使其等于从一个点到另一个点的所有路径的逻辑和。

具体而言，在每个迭代步骤中，我们将过渡矩阵B中的每个元素(i,j)设为:

B[i][j] = B[i][j] || (B[i][k] && B[k][j])

在这里，k是i到j之间的任何一个点。这个式子的意义是，如果从i到k和从k到j都有路径，那么(i,j)在传递闭包中。

迭代继续进行，直到过渡矩阵B的所有元素不变为止。此时，B就包含了所有的传递闭包中的点对，即算法的输出结果。

总的来说，Warshall算法是一种高效的计算图形传递闭包的方法。在实际应用中，这个算法被广泛用于网络流量分析、软件工程等领域。

### 回答3：
Warshall算法是一种求解传递闭包的经典算法。它能在O(n^3)的时间复杂度内求得有向图的传递闭包，其中n是图中节点的个数。要求传递闭包，首先需要明确传递闭包的概念。在有向图G中，若存在一条从节点i到j的有向路径，则称节点i能够到达节点j。传递闭包是指，将所有能够从节点i到达的节点j都标记为可达，这样即得到所有可达性关系的矩阵C。下面具体介绍Warshall算法求传递闭包的步骤：

1.定义一个n*n的布尔型二维数组C，初始化为有向图中的关系矩阵。

2.依次考虑每个节点k，如果节点i可以经过节点k到达节点j，则将其可达性标记为true。

3.使用三重循环遍历关系矩阵，对于每个节点k，如果i到k和k到j都是可达的，则将i到j的可达性标记为true。

4.循环结束后，矩阵C即为有向图的传递闭包。

Warshall算法的核心是三重循环，时间复杂度为O(n^3)。其实现简单，但在大型图中效率不高，C矩阵的存储也需要较大内存空间。如果有向图中存在负环，则无法使用Warshall算法求传递闭包。对于稀疏图，还可以使用Floyd算法的优化版本来求解传递闭包，其时间复杂度为O(n^2.376)。在实际应用中，还有其他算法可用于求解传递闭包，如分治算法、逆序对算法等，根据具体场景选择最适合的算法。

用C++输出warshall算法求关系{1,2,3,4}上{(1,4),(1,1),(2,1),(2,3),(3,1),(3,2),(3,4),(4,2)}的传递闭包的代码

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

#include <stdio.h>

#define N 4

void warshall(int graph[N][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]);
            }
        }
    }
}

int main() {
    int graph[N][N] = {{0, 0, 0, 1},
                       {1, 1, 0, 0},
                       {1, 1, 0, 1},
                       {0, 1, 0, 0}};
    int i, j;

    printf("Original graph:\n");
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }

    warshall(graph);

    printf("\nTransitive closure:\n");
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }

    return 0;
}

输出结果如下：

Original graph:
0 0 0 1 
1 1 0 0 
1 1 0 1 
0 1 0 0 

Transitive closure:
1 1 0 1 
1 1 0 1 
1 1 0 1 
0 1 0 0 

其中，`graph` 表示原始的有向图，`warshall()` 函数实现了Warshall算法，`main()` 函数中则先输出原始图，再输出传递闭包。