When are adjacency lists or matrices the better choice? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-17T19:06:51Z https://cs.stackexchange.com/feeds/question/79322 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/79322 13 When are adjacency lists or matrices the better choice? user21312 https://cs.stackexchange.com/users/68390 2017-07-25T17:08:02Z 2018-01-13T07:48:09Z <p>I was told that we would use a list if the graph is <em>sparse</em> and a matrix if the graph is <em>dense</em>. 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?</p> <p>Thanks in advance!</p> https://cs.stackexchange.com/questions/79322/-/79326#79326 16 Answer by fade2black for When are adjacency lists or matrices the better choice? fade2black https://cs.stackexchange.com/users/72943 2017-07-25T17:55:28Z 2017-07-26T01:43:48Z <p>First of all note that <em><a href="https://en.wikipedia.org/wiki/Dense_graph#Sparse_and_tight_graphs" rel="noreferrer">sparse</a></em> means that you have very few edges, and <em><a href="https://en.wikipedia.org/wiki/Dense_graph" rel="noreferrer">dense</a></em> 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. </p> <p>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$. <br> But if we use adjacency list then we have an array of nodes and each node points to its adjacency list <strong>containing ONLY its neighboring nodes</strong>. </p> <p>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.</p> <p>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.</p> <p>In terms of space complexity<br> Adjacency matrix: $O(n^2)$<br> Adjacency list: $O(n + m)$<br> where $n$ is the number nodes, $m$ is the number of edges.</p> <p>When the graph is undirected tree then<br> Adjacency matrix: $O(n^2)$<br> Adjacency list: $O(n + n)$ is $O(n)$ (better than $n^2$) <br></p> <p>When the graph is directed, complete, with self-loops then<br> Adjacency matrix: $O(n^2)$<br> Adjacency list: $O(n + n^2)$ is $O(n^2)$ (no difference) <br></p> <p>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$.</p> https://cs.stackexchange.com/questions/79322/-/79329#79329 3 Answer by Charles for When are adjacency lists or matrices the better choice? Charles https://cs.stackexchange.com/users/46712 2017-07-25T19:03:47Z 2018-01-13T07:48:09Z <p>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?</p> <p>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 <em>really</em> long, why not just use a matrix to condense it? </p> <p>The reasoning behind list vs matrix really is that simple in this case.</p> <p>P.S. a list is really just a single column matrix!!! (trying to show you just how arbitrary of a decision/scenario this is)</p> https://cs.stackexchange.com/questions/79322/-/79347#79347 2 Answer by Pseudonym for When are adjacency lists or matrices the better choice? Pseudonym https://cs.stackexchange.com/users/6553 2017-07-26T01:47:06Z 2017-07-31T23:31:19Z <p>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.</p> <p>How many bits do you actually need, though?</p> <p>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}$.</p> <p>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.</p> <p>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:</p> <p>$$\log_2 {N^2 \choose E}$$ $$= \log_2 \frac {(N^2)!} {E! (N^2 - E)!}$$ $$= 2E \log_2 N + O(\hbox{low order terms})$$</p> <p>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.</p> <p>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.</p>