Aka*_*ani 10 memory-management time-complexity graph-algorithm
这个陈述有效吗？
"对于有向图和无向图,邻接列表表示具有所需的特性,即它所需的存储量是O(V + E)."
来源:算法介绍,cormen.
pka*_*zak 15
假设您将邻接列表存储在数组中,即
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当且仅当该图是一组被称为阿甘不相交的树.