O（| V | + | E |）内の隣接リストの逆数

Question

G =（V、E）を隣接リスト形式で与えられた有向グラフとします。有向グラフG '=（V、E'）ここで、エッジ（u、v）∈E ' が（v、u）∈Eならば（G'はG ）。 O（| V | + | E |）時間内にG ' の隣接リスト表現 を取得するアルゴリズムを記述します。

簡単な方法で隣接リストを逆にする方法はありますか？

はそれがあった場合は言う：

a-> b 
b-> de 
c-> c 
d-> ab 
e-> 

へ：

a-> d 
b-> ad 
c-> c 
d-> ab 
e-> b 

Answer 1

のは、次のようにグラフにすべての頂点の隣接リストを反復しましょう。

for each u in V: 
    for each v in adjacency_list[u]: 
     reverse_adjacency_list[v].append(u) 

この方法では、すべての| V |の隣接リストをトラバースします。あなたのアルゴリズムの全体的な複雑さに、O（| V |）を寄稿しています。また、これらの隣接リストをすべてトラバースすると、は、グラフのすべてのエッジを効果的にトラバースします。つまり、横断するすべての隣接リストを連結した場合、その結果のリストの長さは| E |となります。したがって、別のO（| E |）は全体の複雑さに寄与する。

したがって、時間の複雑さはこのかなり標準的なアプローチでO（| V | + | E |）になります。この複雑さを達成するために、独自の方法を考案する必要はありません。