1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Came to what conclusion? To the conclusion that the space requirement for the adjacency list representation is $\Theta(V+E)$? This is explained in many textbooks -- where have you looked, and what have you tried? What do you think the space requirement for the adjacency list representation is? (Also I'm not clear on what the preamble about sparse and dense has to do with this.) You haven't given us a lot to work with, so it's a bit tricky to tell where you are going wrong. $\endgroup$ – D.W. Nov 4 '15 at 5:59
  • $\begingroup$ @D.W. Check the last line, that's what I have concluded. The preamble is about the background of the question as well as to let you know that I am done some reading. The link of the reference book is already given in the first line. I am not sure what are you confused about. $\endgroup$ – CodeYogi Nov 4 '15 at 6:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can see fundamental mistake above, I am multiplying the complexities. I think I am stuck with some wrong analogy here, for example suppose there are N buckets and each bucket has M flowers then total number of flowers are NM, what you are saying is it should be N+M, surely I am stuck to some faulty metal model, please rescue me :) $\endgroup$ – CodeYogi Nov 4 '15 at 6:12
  • 2
    $\begingroup$ @CodeYogi, suppose there are $N$ buckets and a total of $M$ flowers distributed across the buckets, and each bucket costs \$1 and each flower costs \$1. What's the total cost? Answer: $N+M$, not $N \times M$. Now think of each bucket as a pointer associated with a single vertex, and each flower as a node in one of the adjacency lists. $\endgroup$ – D.W. Nov 4 '15 at 6:39
2
$\begingroup$

You seem to be confusing the behaviour of a specific graph with the worst-case behaviour. A specific digraph has some given edge set $E$. $|E|$ could be as big as $|V|(|V|-1)$ but it could be much smaller.

To represent a specific digraph using adjacency lists, you need one list per vertex. The list for vertex $x$ contains every vertex $y$ such that $(x,y)$ is an edge. This means that every edge causes exactly one entry in the adjacency lists: it means that $y$ is in $x$'s list. So, for a specific digraph $(V,E)$, you need $|V|$ lists and the total number of entries will be $|E|$. That means the total cost is $|V|+|E|$. (Why not just $|E|$? Because some of the lists might be empty but it still takes some space to say "This list is empty.")

Now, in the worst case, $|E|$ could be as big as $|V|(|V|-1)$ but that's irrelevant: the space you need is $O(|V|+|E|)$, whether $|E|$ takes its maximum possible value or any other value.

$\endgroup$
  • 1
    $\begingroup$ I think more specifically for the undirected graph the total number of entries in adjacency list is 2|E| since each edge will be represented twice. $\endgroup$ – CodeYogi Nov 21 '15 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.