Warshall算法求传递闭包

发布时间：2023-05-20

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算法求出其传递闭包： 接下来我们进行详细的求解步骤：

第一步、复制原始矩阵，得到初始传递闭包矩阵：

0 1 0
0 0 1
1 0 0

第二步、更新矩阵元素，寻找经过节点1的路径：

1 1 0
0 0 1
1 0 0

第三步、更新矩阵元素，寻找经过节点2的路径：

1 1 1
0 0 1
1 0 0

得到最终的传递闭包矩阵，即所有可以到达的节点：

1 1 1
0 0 1
1 0 0

五、Warshall算法求传递闭包例题

下面是一个关系图，求它的传递闭包： 按照Warshall算法的步骤进行计算，得到最终传递闭包矩阵：

1 1 1 1 0
0 1 0 1 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1

六、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算法的步骤进行计算，得到最终传递闭包矩阵：

1 1 1 1 1
0 1 0 1 1
0 0 1 1 0
0 0 0 1 1
0 0 0 0 1

例题2：

给出以下关系矩阵，求它的传递闭包。 解题思路： 按照Warshall算法的步骤进行计算，得到最终传递闭包矩阵：

1 1 1
1 1 1
0 0 1

九、离散传递闭包Warshall

Warshall算法求解传递闭包是离散数学中的重要知识点，在计算机科学中被广泛应用，在深入学习这一算法时，需要了解离散传递闭包的相关内容，深入理解这一知识点的思想和应用。

推荐文章