Warshall算法求傳遞閉包

一、Warshall算法求傳遞閉包原理

傳遞閉包是一種二元關係，指的是從集合中的一個元素到另一個元素存在一條路徑，傳遞閉包就是將這些路徑全部提取出來，構成一個新的關係。在計算機科學中，我們常常需要求傳遞閉包來解決問題，如在編譯原理中用到的數據流分析、在圖論中用到的最短路徑等等。

Warshall算法是一種計算傳遞閉包的方法，通過對原始關係矩陣進行變換，不斷更新矩陣元素，最終得到傳遞閉包矩陣。

二、Warshall算法求傳遞閉包視頻

以下視頻為一份關於Warshall算法求傳遞閉包的簡單介紹，可以幫助深入理解算法原理和改進方法。

<iframe width="560" height="315" src="https://www.youtube.com/embed/118pFb8Sqg4" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

三、Warshall算法求傳遞閉包C代碼

以下是求解傳遞閉包的Warshall算法的C語言實現：

void FloydClosure(int edge[M][M], int n, int ans[M][M]) {    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            ans[i][j] = edge[i][j];        }    }    for (int k = 0; k < n; k++) {        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                ans[i][j] = ans[i][j] || (ans[i][k] && ans[k][j]);            }        }    }}

四、Warshall算法求傳遞閉包圖解

下圖為一個簡單的關係矩陣，我們可以通過Warshall算法求出其傳遞閉包：

接下來我們進行詳細的求解步驟：

第一步、複製原始矩陣，得到初始傳遞閉包矩陣：

第二步、更新矩陣元素，尋找經過節點1的路徑：

第三步、更新矩陣元素，尋找經過節點2的路徑：

得到最終的傳遞閉包矩陣，即所有可以到達的節點：

五、Warshall算法求傳遞閉包例題

下面是一個關係圖，求它的傳遞閉包：

按照Warshall算法的步驟進行計算，得到最終傳遞閉包矩陣：

六、Warshall算法求傳遞閉包證明

我們可以用歸納法證明Warshall算法求解傳遞閉包的正確性，即假設對一個n*n的矩陣進行初步判斷求解。

1.當n=2時，易知矩陣更新的結果一定是正確的。

2.假設當矩陣大小為n*n時，Warshall算法求解傳遞閉包的結果正確，即到此時我們可以確保如下組合方程的正常運算：

ans[i][j] = edge[i][j] || (edge[i][k] && edge[k][j]);(i,j,k=1,2,…,n)

3.考慮n+1的情況，對於新加入的點p，對於已經存在的點i，在不經過p的情況下的傳遞性一定是正確的，因此warshall在更新關係矩陣時並不會對已經正確的傳遞性進行更新。對於過p的情況，我們需要對矩陣進行如下的運算：

ans[i][j]=ans[i][j] || (ans[i][p] && ans[p][j]);(i,j=1,2,…,n+1)

由歸納假設，我們可以得到在n的情況下已經求得的ans矩陣一定是正確的，那麼在加入了點p的時候，由於ans[p][p]的初始值為1，所以ans[p][p]值一定不會被更新，故可以放心進行判斷。

七、Warshall算法求傳遞閉包離散數學

Warshall算法求傳遞閉包在計算機科學中有着廣泛的應用，同時在離散數學中同樣也有很多相關的知識點。在學習離散數學的時候，通過Warshall算法的學習，可以更加深入理解傳遞閉包這一概念，同時也為後續的內容奠定了基礎。

八、Warshall算法例題

例題1：給出以下關係，求它的傳遞閉包。

解題思路：

按照Warshall算法的步驟進行計算，得到最終傳遞閉包矩陣：

例題2：給出以下關係矩陣，求它的傳遞閉包。

解題思路：

按照Warshall算法的步驟進行計算，得到最終傳遞閉包矩陣：

九、離散傳遞閉包Warshall

Warshall算法求解傳遞閉包是離散數學中的重要知識點，在計算機科學中被廣泛應用，在深入學習這一算法時，需要了解離散傳遞閉包的相關內容，深入理解這一知識點的思想和應用。