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

Question

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

这是我想出的算法:

对于顶点中的顶点
对于邻居中的邻居
对于邻居中的 n
如果(n!=邻居)
然后-> if(n.value==neighbor)
将其添加到新的邻接列表
休息;//这意味着我们在顶点和邻居之间找到了一条大小为 2 的路径
否则继续

Answer 1

使用BFS 可以在O(VE) 时间内解决问题(广度优先搜索)。关于BFS的事情, 是它遍历图 level by level .这意味着首先它遍历所有顶点 distance of 1来自 source vertex .然后遍历distance of 2处的所有顶点来自 source vertex等等。所以我们可以利用这个事实终止我们的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 开始使用新的数据结构。遍历。