计算有向图的平方的算法（以邻接表的形式表示）-Java 学习之路

我正在构建一个算法来计算有向图的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的路径
否则继续

1 回答

4
问题可以使用 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 遍历的新数据结构开始 .
回复于 2024-04-20T21:32:59+08:00

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

1 回答

相关问题