T O P

[资源分享]     waeshall算法原理和实现

  • By - 楼主

  • 2020-11-16 20:40:35
  • 传递闭包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];
                    }
                }
            }
        }
    }
    
    

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册