用JAVA中的Warshall计算M矩阵的t（R）（传递矩阵）

Warshall算法是一种用于计算图中传递闭包的算法，其中传递闭包是指对于图中的任意两个顶点i和j，如果存在一条从i到j的路径，则i和j之间存在一条有向边。M矩阵也被称为传递矩阵，它是一个二维数组，其中第i行第j列的元素为1表示从顶点i到j存在一条路径，否则为0。

在Java中，可以使用Warshall算法计算传递闭包，具体步骤如下：
1.初始化传递矩阵t为原始邻接矩阵R。
2.对于每个顶点k，执行以下步骤：
a.对于每个顶点i，执行以下步骤：
i.如果t[i][k]为1，则对于每个顶点j，将t[i][j]设置为t[i][j]或t[k][j]。
3.当所有顶点都被遍历过后，t就是传递闭包矩阵M。

相关问题

java编程求一个关系的闭包，传递闭包用warshall或邻接矩阵乘法方法。

假设给定一个关系为R的邻接矩阵A，其中A[i][j]=1表示i与j有关系，A[i][j]=0表示i与j无关系。那么R的传递闭包可以通过Warshall算法或邻接矩阵乘法方法计算得到。

1. Warshall算法

Warshall算法是通过一个二重循环来实现的，外循环控制中间点，内循环控制起点和终点，具体如下：

public static int[][] transitiveClosure(int[][] A) {
    int n = A.length;
    int[][] R = new int[n][n];
    // 初始化R为A
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            R[i][j] = A[i][j];
        }
    }
    // 计算传递闭包
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (R[i][k] == 1 && R[k][j] == 1) {
                    R[i][j] = 1;
                }
            }
        }
    }
    return R;
}

2. 邻接矩阵乘法方法

邻接矩阵乘法方法是通过矩阵乘法来实现的，具体如下：

public static int[][] transitiveClosure(int[][] A) {
    int n = A.length;
    int[][] R = new int[n][n];
    // 初始化R为A
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            R[i][j] = A[i][j];
        }
    }
    // 计算传递闭包
    for (int k = 0; k < n; k++) {
        int[][] temp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < n; l++) {
                    temp[i][j] |= R[i][l] & A[l][j];
                }
            }
        }
        R = temp;
    }
    return R;
}

以上两种方法都是通过对矩阵A进行若干次操作得到传递闭包矩阵R。其中Warshall算法的时间复杂度为O(n^3)，邻接矩阵乘法方法的时间复杂度为O(n^4/log n)，但是邻接矩阵乘法方法可以通过矩阵快速幂的优化来减少时间复杂度。

离散数学中用warshall算法（由邻接矩阵计算可达矩阵）

Warshall算法是一种计算有向图可达矩阵的经典算法，它的基本思想是动态规划。假设 $A$ 是一个 $n\times n$ 的邻接矩阵，$R$ 是可达矩阵，$r_{i,j}$ 表示从顶点 $i$ 到顶点 $j$ 是否存在一条路径。Warshall算法的核心是以下递推式：

$$r_{i,j}=\begin{cases}
1, & i=j \text{ 或 } a_{i,j}=1 \\
r_{i,k}\land r_{k,j}, & \text{otherwise}
\end{cases}$$

其中，$\land$ 表示逻辑与运算。上述递推式表示，如果 $i=j$ 或者 $i$ 到 $j$ 有一条边，则 $r_{i,j}=1$；否则，$r_{i,j}$ 就等于 $i$ 到 $k$ 存在路径且 $k$ 到 $j$ 存在路径的逻辑与。

根据这个递推式，可以通过以下 Warshall 算法来计算可达矩阵：

for k from 1 to n do
    for i from 1 to n do
        for j from 1 to n do
            r_{i,j} = r_{i,j} or (r_{i,k} and r_{k,j})

其中，$\text{or}$ 表示逻辑或运算，$\text{and}$ 表示逻辑与运算。上述算法中的三重循环分别枚举 $k$、$i$、$j$，每次更新 $r_{i,j}$ 的值。算法的时间复杂度是 $O(n^3)$，空间复杂度是 $O(n^2)$。

Warshall算法在离散数学中应用广泛，可以用于计算有向图的可达性、传递闭包等问题。它的优点是实现简单、时间复杂度低，可以处理大规模的图。