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

我正在构建计算有向图的G^2的算法，该有向图是一个邻接表的形式，其中G^2 = （V，E'），其中如果在G中u和v之间存在长度为2的路径，那么E'被定义为（u，v）∈E'。我非常了解这个问题并找到了一个我假设的算法是正确的，但是我的算法的运行时间是O（VE^2），其中V是顶点的数量，E是图的边数。我想知道如何在O（VE）时间内做到这一点，以提高效率？计算有向图的平方的算法（以邻接表的形式表示）

这里的算法，我想出了：在邻居

顶点顶点中
邻居在N个相邻

如果（！N =邻居）
则 - >如果（ n.value == neighbor）
将此添加到新的邻接列表
break; //这意味着我们已经找到顶点和邻居之间大小为2的路径
否则

来源

2017-04-10 smriti

的问题是可以解决的继续时间O（VE）使用BFS（广度优先搜索）。关于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的新数据结构开始。

来源

2017-04-10 04:35:27

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

回答

相关问题