计算有向图平方的算法（以邻接表的形式表示）

Question

我正在构建一种算法来计算作为邻接表形式的有向图的 G^2，其中 G^2 = (V,E')，其中 E' 定义为 (u,v)?E ? 如果 G 中的 u 和 v 之间有一条长度为 2 的路径。我很好地理解了这个问题，并找到了一个我认为是正确的算法，但是我的算法的运行时间是 O(VE^2)，其中 V 是数字顶点数，E 是图的边数。我想知道如何在 O(VE) 时间内做到这一点，以使其更有效率？

这是我想出的算法：

在顶点的顶点
的邻居在邻居
的邻居对于n
如果（！N =邻居）
则─>如果（n.value ==邻居）
它添加到一个新的邻接表
中断; // 这意味着我们在顶点和邻居之间找到了一条大小为 2 的路径，
否则继续

Answer 1

该问题可以使用（广度优先搜索）在O(VE)时间内解决BFS。的事情BFS，是它遍历图形level by level。这意味着首先它从 遍历 adistance of 1处的所有顶点source vertex。然后它遍历 adistance of 2处的所有顶点，source vertex依此类推。因此BFS，当我们到达 a 处的顶点时，我们可以利用这一事实并终止我们的distance of 2。

以下是伪代码：

For each vertex v in V
{
 Do a BFS with v as source vertex
 {
  For all vertices u at distance of 2 from v
  add u to adjacency list of v 
  and terminate BFS
 }
}

由于BFS需要时间O(V + E)并且我们为每个顶点调用它，所以总时间是O(V(V + E)) = O(V^2 + VE) = O(VE)。请记住从每次BFS遍历都有新的数据结构。