[Solved]: Space complexity of directed and undirected graph

Problem Detail: 

I have started reading graph theory from Introduction to Algorithm. The author starts by saying that if the graph is dense then:

$$|E|\text{ close to }|V|^2$$ else if the graph is sparse then:

$$|E|\text{ is much less than }|V^2|$$

According to me the above two relations makes sense in respect of a complete graph where the total number of edges is $\frac{(V)*(V-1)}{2}$ hence, $E = O(V^2)$.

Hence, we choose adjacency list representation where the length of the list is $\text{2|E|}$ for undirected graph and $\text{|E|}$ for directed graph. After that he simple concludes that space requirement for the adjacency list representation is $\Theta(V+E)$. I am really stuck on how he came to this conclusion without any explanation. According to me it should be $O(V*(V-1))$ because for each vertex the maximum possible edge is $V-1$. What I am doing wrong?

Asked By : CodeYogi

Answered By : D.W.

It's hard to know for sure from what you've written, but I suspect what you're doing wrong is that you're considering what the space requirement would be for a complete graph. For a complete graph, the space requirement for the adjacency list representation is indeed $\Theta(V^2)$ -- this is consistent with what is written in the book, as for a complete graph, we have $E=V(V-1)/2 =\Theta(V^2)$, so $\Theta(V+E)=\Theta(V^2)$.

However, you shouldn't limit yourself to just complete graphs. There are other graphs that aren't complete, and have fewer edges than the complete graph. In general, the space for the adjacency list representation is $\Theta(V+E)$; this fact holds for all graphs, regardless of how many edges they have.

Why is this true? It's because for each vertex you have a pointer to the head of a linked list. That's $\Theta(V)$ space for all of those pointers. Also, the total number of nodes across all the linked lists is equal to $2E$, as each edge $(u,v)$ appears twice: once in the list for $u$, and once in the list for $v$. Therefore the space needed for all of the linked lists is $\Theta(E)$. Adding the space for the pointers and the space for the lists gives $\Theta(V+E)$.

---

You could say that the space requirement for the adjacency list is $O(V^2)$. It's true that it will never be more than that. However, for some graphs it will be much less. For instance, in a graph that is a simple path ($v_1 \to v_2 \to \dots \to v_n$), there are $V$ vertices and $E=V-1$ edges in total. For that graph, the adjacency list representation will need $\Theta(V+E)=\Theta(V)$ space. Thus the $O(V^2)$ upper bound is very loose and too pessimistic.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49062