11
$\begingroup$

I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the natural choice to make?

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Related: stackoverflow.com/a/2218331/5746050 and stackoverflow.com/a/5419933/5746050 $\endgroup$ – ryan Jul 25 '17 at 17:20
  • $\begingroup$ That's not a definition, mostly because there's no single definition of "sparse" and "dense". Also, there are other considerations, e.g. which aspects of the graph you access how often. $\endgroup$ – Raphael Jul 25 '17 at 17:23
  • $\begingroup$ @Raphael Can you go into more details about the other considerations? $\endgroup$ – user21312 Jul 25 '17 at 17:27
  • 1
    $\begingroup$ @user21312, a big difference is iterability vs access of edges. If you often need to iterate over edges then adj list might be more useful. If you often need to determine if an edge exists or access its weight (or other info) then matrix might be better. $\endgroup$ – ryan Jul 25 '17 at 17:30
  • $\begingroup$ For your purpose, we probably could careless about what is the definition of 'sparse' and 'dense'. Just model the time complexity of matrix operation you want to use for each types of datastructure and see where the 'break point of density' is. I think the second link by @ryan is trying to do something similar $\endgroup$ – Billiska Jul 25 '17 at 17:32
14
$\begingroup$

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph. In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes.

Now, when we use matrix representation we allocate $n\times n$ matrix to store node-connectivity information, e.g., $M[i][j] = 1$ if there is edge between nodes $i$ and $j$, otherwise $M[i][j] = 0$.
But if we use adjacency list then we have an array of nodes and each node points to its adjacency list containing ONLY its neighboring nodes.

Now if a graph is sparse and we use matrix representation then most of the matrix cells remain unused which leads to the waste of memory. Thus we usually don't use matrix representation for sparse graphs. We prefer adjacency list.

But if the graph is dense then the number of edges is close to (the complete) $n(n-1)/2$, or to $n^2$ if the graph is directed with self-loops. Then there is no advantage of using adjacency list over matrix.

In terms of space complexity
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + m)$
where $n$ is the number nodes, $m$ is the number of edges.

When the graph is undirected tree then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n)$ is $O(n)$ (better than $n^2$)

When the graph is directed, complete, with self-loops then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n^2)$ is $O(n^2)$ (no difference)

And finally, when you implement using matrix, checking if there is an edge between two nodes takes $O(1)$ times, while with an adjacency list, it may take linear time in $n$.

$\endgroup$
  • $\begingroup$ "while with an adjacency list, it may take linear time" - Given that your adjacency list (probably) lacks any natural order, why is it a list instead of a hash set? $\endgroup$ – Kevin Jul 26 '17 at 5:54
  • 1
    $\begingroup$ @Kevin Then it would be called "adjacency hash" instead of "list". Also possible, why not? But if you simply do DFS or BFS, or some other procedure that scans systematically all nodes then what is advantage of using hash over list? In any case you would inspect all adjacent nodes. $\endgroup$ – fade2black Jul 26 '17 at 6:06
  • 3
    $\begingroup$ I would add that in the unweighted undirected case, for a nearly complete graph it might be more feasible to store its complement, i.e. a sparse graph. So a matrix is useful when approximately half of the edges are present. $\endgroup$ – M. Winter Jul 27 '17 at 8:27
3
$\begingroup$

To answer by providing a simple analogy.. If you had to store 6oz of water, would you (generally speaking) do so with a 5 gallon container, or an 8oz cup?

Now, coming back to your question.. If the majority of your matrix is empty, then why use it? Just list each value instead. However, if your list is really long, why not just use a matrix to condense it?

The reasoning behind list vs matrix really is that simple in this case.

P.S. a list is really just a single column matrix!!! (trying to show you just how arbitrary of a decision/scenario this is)

$\endgroup$
2
$\begingroup$

Consider a graph with $N$ nodes and $E$ edges. Ignoring low-order terms, a bit matrix for a graph uses $N^2$ bits no matter how many edges there are.

How many bits do you actually need, though?

Assuming that edges are independent, the number of graphs with $N$ nodes and $E$ edges is ${N^2 \choose E}$. The minimum number of bits required to store this subset is $\log_2 {N^2 \choose E}$.

We will assume without loss of generality that $E \le \frac{N^2}{2}$, that is, that half or fewer of the edges are present. If this is not the case, we can store the set of "non-edges" instead.

If $E = \frac{N^2}{2}$, $\log_2{N^2 \choose E} = N^2 + o(N^2)$, so the matrix representation is asymptotically optimal. If $E \ll N^2$, using Stirling's approximation and a little arithmetic, we find:

$$\log_2 {N^2 \choose E}$$ $$= \log_2 \frac {(N^2)!} {E! (N^2 - E)!}$$ $$= 2E \log_2 N + O(\hbox{low order terms})$$

If you consider that $\log_2 N$ is the size of an integer which can represent a node index, the optimal representation is an array of $2E$ node ids, that is, an array of pairs of node indexes.

Having said that, a good measure of sparsity is the entropy, which is also the number of bits per edge of the optimal representation. If $p = \frac{E}{N^2}$ is the probability that an edge is present, the entropy is $- \log_2{p(1-p)}$. For $p \approx \frac{1}{2}$, the entropy is 2 (i.e. two bits per edge in the optimal representation), and the graph is dense. If the entropy is significantly greater than 2, and in particular if it's close to the size of a pointer, the graph is sparse.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .