memory-management - 邻接表表示所需的内存如何是 O(V+E)？

Question

这个声明如何有效？

“对于有向图和无向图，邻接表表示具有理想的特性，即它需要的内存量为 O(V+E)。”

资料来源:算法介绍，cormen。

Answer 1

假设您将邻接列表存储在一个数组中，即

edges[v] represents a list of edges outgoing from v

为了测量空间复杂度，首先请注意您正好有 V数组中的记录，每个顶点一个。所以你正在使用 O(V)仅用于存储空列表的内存。

接下来，请注意，如果图是有向图，则每个边在这些列表的数组中只出现一次。

如果图是无向图，则每条边在这些列表的数组中恰好出现两次。

在这两种情况下，整个数组中的条目数最多以 2 * E = O(E) 为界。 .

放在一起，我们看到内存的总数以 O(V + E)为界。与 O(max(V, E)) 相同.

术语 V超越 E当且仅当图是一组不相交的树，称为forrest。