waeshall算法原理和实现
传递闭包Warshall方法简要介绍
① 在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的n×n二值矩阵，则传递闭包的矩阵B+可如下计算： B+ = B + B2 + B3 + ……+ (B)n
② 式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为B，B(B)，B(BB)，B(BBB)，……，所以在运算的每一步我们只需简单地把现有结果乘以B。
warshall算法的运算规则
其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：
（1）置新矩阵A=M;
（2）置k=1;
（3）对所有i如果A[i,k]=1，则对j=1..n执行：
A[i,j]←A[i,j]∨A[k,j];
（4）k增1;
（5）如果k≤n，则转到步骤（3），否则停止。
所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。
warshall算法的实现
public class Warshall {
static int[][] warshall={
{0,1,1,0},
{0,0,1,0},
{0,0,0,1},
{0,0,1,0}
};
public static void main(String[] args) {
display(warshall);
setWarshell(warshall);
System.out.println("经过算法闭包之后输出");
display(warshall);
}
//打印矩阵
public static void display(int[][] warshall){
for (int i = 0; i < warshall.length; i++) {
for (int j=0;j<warshall.length;j++){
System.out.print(warshall[i][j]+" ");
}
System.out.println();
}
}
//warshall算法实现
public static void setWarshell(int[][]warshall){
for (int k = 0; k < warshall.length; k++) {
for (int i = 0; i < warshall.length; i++) {
for (int j = 0; j < warshall.length; j++) {
warshall[i][j]|=warshall[i][k]*warshall[k][j];
}
}
}
}
}
