该声明如何有效？
“对于有向图和无向图，邻接表表示具有理想的特性，即它需要的内存量是 O(V+E)。”
资料来源：算法简介，cormen。
问问题
8555 次
2 回答
18
假设您将邻接列表存储在一个数组中，即
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
于 2013-10-18T11:53:16.317 回答
0
我想你可以这样想，如果你有 10 个顶点和 30 条边，那么让 v 和 E 代表你存储每个顶点和边所需的存储空间。
10(V+E)<=(10V+30E)<=30(V+E)
根据上述等式，您可以得出结论，它需要Ѳ(V+E) 空间。
于 2015-07-03T21:40:12.227 回答