O(|V | + |E|) 中邻接表的逆
inverse of adjacency list in 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| 的邻接表顶点，这对算法的整体时间复杂度贡献了 O(|V|)。此外，当您遍历所有这些邻接表时，您实际上遍历了图中的所有边。换句话说，如果将遍历的所有邻接列表连接起来，则结果列表的长度将为 |E|。因此，另一个 O(|E|) 对整体复杂性有贡献。
因此，使用这种非常标准的方法，时间复杂度将为 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| 的邻接表顶点，这对算法的整体时间复杂度贡献了 O(|V|)。此外，当您遍历所有这些邻接表时，您实际上遍历了图中的所有边。换句话说，如果将遍历的所有邻接列表连接起来，则结果列表的长度将为 |E|。因此，另一个 O(|E|) 对整体复杂性有贡献。
因此，使用这种非常标准的方法，时间复杂度将为 O(|V| + |E|)，您无需设计任何特殊方法来实现这种复杂性。