Warshall算法

你的名字 2024-04-26 11:08 70阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：> [算法][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  什么是传递闭包？
 *  Warshall算法的原理
 *  完整伪代码：
 *  总结：

## 前言 ##

Warshall算法是一种经典的**图论算法**，用于计算给定有向图的传递闭包。在本文中，我们将详细介绍Warshall算法，并通过图例来演示算法的执行过程。

## 什么是传递闭包？ ##

![在这里插入图片描述][483b46486eda481e8775a5f1323c7ab3.png]

在离散数学中，如果存在一个有向图中的节点u可以**直接和间接到达另一个节点v**，则称u可以到达v。如果对于图中的所有节点对(u,v)，都存在一条从u到v的有向路径，则称该图是传递的。传递闭包则表示所有可达性的集合。

## Warshall算法的原理 ##

在我们写程序**计算传递闭包**时通常会这样写：  
![在这里插入图片描述][8b861db002014e87b3c076aed94c1bda.png]  
  这样的时间复杂度为**O(n^4)**,为了简化该算法的复杂度，**Warshall算法使用动态规划的思想**，通过多次迭代，计算有向图的传递闭包。  
**具体算法：**

*  初始化可达矩阵。将可达矩阵的值初始化为邻接矩阵的值。
 *  逐步构建可达矩阵。对于每一对顶点i和j，如果存在一条从i到j的路径或者存在一条从i到k的路径和一条从k到j的路径，那么我们就可以说顶点i可达顶点j。

因此，我们可以使用以下公式来逐步构建可达矩阵。

T[i][j]=T[i][j]||(T[i][k]&&T[k][j];

其中，reach\[i\]\[j\]表示从顶点i是否可达顶点j，k是一个介于1和n之间的中间顶点。

最终可达矩阵即为该图的传递闭包。

## 完整伪代码： ##

![在这里插入图片描述][124a09c58ed343ab95cfc3b754c36d54.png]

## 总结： ##

其实简单的说，传递闭包就是让“间接到达”变成直接到达。所以我们通过k遍历了所有的间接情况，通过∪和∩得到了最后的矩阵。

更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [c语言学习][c]  
> [算法][Link 1]  
> [智力题][Link 4]  
> [初阶数据结构][Link 5]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/1a33c3cf39784af6895ec6fa8757dca6.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/45427d2ea7bb486db7adeab3bce31860.gif
[483b46486eda481e8775a5f1323c7ab3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/c71fb55b262542dc9c6fcd7fb062c275.png
[8b861db002014e87b3c076aed94c1bda.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/6db613b1f9ad435abdfe1956e5981378.png
[124a09c58ed343ab95cfc3b754c36d54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/91e35527e81843b5b8ad967743cc8453.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12166402.html
[Link 5]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e199fb5f493849d3a0de6ea8b8d0bfbb.gif