计算有向图平方的算法(以邻接列表的形式表示)

Question

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

这是算法，我想出了：

对于顶点
中的顶点 对于邻居中的邻居
对于邻居
中的 n if(n！=邻居(
then-> if(n.value==neighbor(
将其添加到新的邻接列表
破;这意味着我们在顶点和邻居
之间找到了大小为 2 的路径 否则继续

Answer 1

这个问题可以使用BFS(广度优先搜索(在时间O(VE(中解决。关于BFS的事情是，它遍历图level by level。这意味着它首先遍历距离source vertex distance of 1的所有顶点。然后，它以距离source vertex distance of 2遍历所有顶点，依此类推。所以我们可以利用这个事实并终止我们的BFS，当我们到达顶点时 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遍历的新数据结构开始。