隣接リストの形式である有向グラフのG^2を計算するためのアルゴリズムを構築しようとしています。ここで、G^2 = （u、v）∈E 'と定義される。ここで、uとvとの間にGの長さ2のパスがあるとすると、（V、E'）私のアルゴリズムのランタイムはO（VE^2）です。ここで、Vは頂点の数、Eはグラフの辺の数です。より効率的にするためにO（VE）時間にこれをどうやってやることができるのだろうと思っていましたか？ （！N =隣人）
then-場合（場合>隣人
におけるnの隣人
に隣人のために頂点
に頂点のため隣接グラフの二乗を計算するアルゴリズム
：ここ
はアルゴリズムであり、私が思い付きましたn.value == neighbor）
これを新しい隣接リストに追加
break; //これは、頂点と隣接
間のサイズ2の経路を発見した意味さもなければ
問題が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トラバーサルごとに新しいデータ構造から始めてください。