一、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算法求解传递闭包是离散数学中的重要知识点，在计算机科学中被广泛应用，在深入学习这一算法时，需要了解离散传递闭包的相关内容，深入理解这一知识点的思想和应用。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/293635.html
微信扫一扫 
支付宝扫一扫 