計算有向圖的平方的算法（以鄰接表的形式表示）

Question

我正在構建計算有向圖的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的路徑
否則

Answer 1

的問題是可以解決的繼續時間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的新數據結構開始。