waeshall演算法原理和實現

• 2020 年 11 月 16 日
• 筆記
• 數據結構與演算法

傳遞閉包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];
                }
            }
        }
    }
}