1
$\begingroup$

I know from the book by Neapolitan that for any algorithm input size is defined as the number of bits to encode the input. In graph algorithms, the input size is defined as $|V(G)| + |E(G)|$ for the input graph $G$. On the other hand, we save graphs in computers by their either adjacency lists or adjacency matrices which are of size $2|E(G)|$ and $|V(G)|^{2}$. So how is the input size $|V(G)| + |E(G)|$?

$\endgroup$
2
$\begingroup$

The size of adjacency list representation is $\Theta(|E(G)| + |V(G)|)$, and not $\Theta(|E(G)|)$. For example, consider a graph with $n$ vertices and $0$ edges. The adjacency list corresponding to each vertex is empty. But storing the null pointer requires constant space for each vertex. Therefore, the size of the adjacency lists is $|V(G)|$ here.

$\endgroup$
4
  • $\begingroup$ So if we want to compute the (almost) exact size of an undirected graph $G$ which is in adjacency list representation, it's $|V(G)| + 2|E(G)|$. Right? $\endgroup$
    – Emad
    Sep 21 '21 at 5:12
  • $\begingroup$ @Emad For an undirected graph: yes. For a directed graph, precisely it is $|V(G)| + |E(G)|$ . Although it is better to say $\Theta(|V(G)| + |E(G)|)$ for both. $\endgroup$ Sep 21 '21 at 5:22
  • $\begingroup$ And for the adjacency matrix representation, it's $\Theta(|V(G)|^{2})$ for both types? $\endgroup$
    – Emad
    Sep 21 '21 at 5:29
  • $\begingroup$ @Emad right. Always. $\endgroup$ Sep 21 '21 at 5:30

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.