java编程求一个关系的闭包,传递闭包用warshall或邻接矩阵乘法方法。
时间: 2023-06-11 19:10:23 浏览: 134
假设给定一个关系为R的邻接矩阵A,其中A[i][j]=1表示i与j有关系,A[i][j]=0表示i与j无关系。那么R的传递闭包可以通过Warshall算法或邻接矩阵乘法方法计算得到。
1. Warshall算法
Warshall算法是通过一个二重循环来实现的,外循环控制中间点,内循环控制起点和终点,具体如下:
```java
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. 邻接矩阵乘法方法
邻接矩阵乘法方法是通过矩阵乘法来实现的,具体如下:
```java
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),但是邻接矩阵乘法方法可以通过矩阵快速幂的优化来减少时间复杂度。
阅读全文