How is this statement valid?
"For both directed and undirected graphs, the adjacency-list representation has the desirable property that the amount of memory it requires is O(V+E)."
source: introduction to algorithms, cormen.
Let's assume that you are storing adjacency lists in an array, i.e.
edges[v] represents a list of edges outgoing from v
In order to measure the space complexity, firstly just notice that you have exactly V
records in the array, one for each vertex. So you are using O(V)
memory for just storing the empty lists.
Next, notice that if the graph is directed, every edge appears exactly once in the array of those lists.
If the graph is undirected, every edge appears exactly twice in the array of those lists.
In both cases, the number of entries in the whole array is bounded by at most 2 * E = O(E)
.
Putting it together, we see that the total number of memory is bounded by O(V + E)
which is the same as O(max(V, E))
.
The term V
surpasses E
if and only if the graph is a set of disjoint trees which is called a forrest.
I think you can think of it in this way, if you have 10 vertexes and 30 edges, then let v and E stand for the storage you need for storing each vertex and edge.
10(V+E)<=(10V+30E)<=30(V+E)
Based on the above equation, you can conclude it requires Ѳ(V+E) space.