warshall算法求传递闭包java

### 回答1：
B'Warshall算法是一种用于寻找所有节点对之间最短路径的动态规划算法。在Java中实现传递闭包可以使用二维数组来存储图的邻接矩阵，根据Warshall算法的思路，对每个节点进行遍历，利用传递闭包的性质更新邻接矩阵中的元素，最终得到所有节点对之间的最短路径。'

### 回答2：
Warshall算法是一种计算传递闭包的算法，其基本思想是利用一个矩阵记录图中各个点之间的关系，并通过三重循环逐步更新矩阵，最终得到传递闭包矩阵。下面我们来详细介绍如何使用Java实现Warshall算法求传递闭包。

首先，我们需要定义一个表示图的二维矩阵，并将图中相邻点的位置值设置为1，不相邻点的位置值设置为0。如下所示：

int[][] matrix = {
{0, 1, 0, 1},
{0, 0, 1, 0},
{0, 0, 0, 1},
{0, 0, 0, 0}
};

接着，我们定义一个n*n的布尔类型矩阵，表示传递闭包。这个矩阵最初的值与图的二维矩阵相同，如下所示：

boolean[][] closure = {
{false, true, false, true},
{false, false, true, false},
{false, false, false, true},
{false, false, false, false}
};

接下来，我们使用Warshall算法计算出传递闭包。具体做法是遍历矩阵中的每一个位置，如果存在一个点k和点i之间连通，并且点i和点j之间连通，则表示点k和点j之间也连通，于是将closure[k][j]赋值为true。最终，得到的closure数组就是图的传递闭包。代码如下：

for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][k] == 1 && matrix[k][j] == 1) {
closure[i][j] = true;
}
}
}
}

最后，我们打印出传递闭包矩阵，即可得到图的传递闭包。代码如下：

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(closure[i][j] + " ");
}
System.out.println();
}

以上就是使用Java实现Warshall算法求传递闭包的方法。通过Warshall算法，可以快速有效地计算图的传递闭包，避免了一次次深搜或广搜的繁琐工作，提高了程序的效率。

### 回答3：
Warshall算法是求解传递闭包的经典算法之一。在任何有向图中，一些节点之间可能存在传递关系，例如，假设节点i可以到达节点j，节点j可以到达节点k，则节点i也可以到达节点k。传递关系意味着传递闭包，也就是说，在传递闭包中，如果节点i可以到达节点j，节点j可以到达节点k，则节点i也可以到达节点k。

Warshall算法的实现步骤如下：

1. 声明一个二维数组，表示有向图的矩阵形式，其中矩阵的值为1表示存在从i到j的边，为0表示不存在。

2. 嵌套三层循环，依次枚举i、j和k，如果矩阵中存在从i到j和从j到k的边，则将矩阵中从i到k的边置为1。

3. 最终得到的矩阵就是传递闭包。

下面是Java代码实现：

public class Warshall {
public static int[][] transitiveClosure(int[][] graph) {
int n = graph.length;
int[][] closure = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
closure[i][j] = graph[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
closure[i][j] = (closure[i][j] != 0) || ((closure[i][k] != 0) && (closure[k][j] != 0)) ? 1 : 0;
}
}
}
return closure;
}
}

在这个实现中，我们首先复制了输入的graph数组，然后使用三层循环来更新传递闭包。在第三层循环中，我们检查从i到j和从j到k是否存在边，如果存在，则将从i到k的边标记为1。

最后，我们将传递闭包返回给调用者。