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

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

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

处的顶点时终止我们的 BFS

伪代码如下：

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 遍历的新数据结构。

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

Algorithm to Compute square of a directed graph(represented in form of an adjacency list)

algorithm

graph

graph-algorithm