algorithm - O(| V | + | E |)中邻接表的逆

设G=（V，E）是有向图，以邻接列表格式给出定义
有向图G'=（V，E'），其中边（u，V）∈E'
当且仅当（v，u）∈e（即g'反转g中每个边的方向）。描述获取邻接列表表示的算法
G'
在O（| V |+| E |）时间内。
有没有一种简单的方法来反转邻接列表？
如果是：

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

致：

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

最佳答案

假设您按如下方式迭代图中所有顶点的邻接列表。

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

通过这种方法，遍历所有V顶点的邻接表，这对算法的总体时间复杂度有贡献（v）。另外，当遍历所有这些邻接列表时，可以有效地遍历图中的所有边。换句话说，如果将遍历的所有邻接列表串联起来，则结果列表的长度将为| E |因此，另一个O（εE）有助于整体复杂性。
因此，用这种相当标准的方法，时间复杂度将是O（v v + e e），并且不需要设计任何特殊的方法来实现这种复杂性。

关于algorithm - O(| V | + | E |)中邻接表的逆，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40378152/