36 图的传递闭包

解决图可达性的传递闭包

1. 场景

通过图上的深度和广度优先搜索算法，我们可以知道顶点 u 到顶点 v 的可达性问题，但是在某些应用中，我们可能希望更高校的回答很多可达性问题。此时对图预计算一个更高效的表示方式是非常值得的，图的传递闭包就是用来解决这个问题。

有向图 G 的传递闭包是有向 G1 使得 G1 顶点与 G 的顶点一样，并且对于所有顶点对 (u, v) 能直接表示是否有从 u 到 v 的一条路径。