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

Question

设 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

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|)，您无需设计任何特殊方法来实现这种复杂度。