World's most popular travel blog for travel bloggers.

# [Solved]: A Graph's Density and Sparsity

, ,
Problem Detail:
1. A graph is dense when |E| (edges) is closest to $|V|^2$.
2. A graph is sparse when |E| is closer to $|V|$.

What does it mean to take the magnitude of the vertices? Secondly, I am having a hard time conceptualizing why the above two rules are true.

Also can someone elaborate on why if a graph is sparse, it should be represented with an adj list and why if it is dense, it is best to use an adjacency matrix instead?

The notation $|V|$ here means the number of vertices in your graph. Likewise, $|E|$ is used to denote the number of edges. We typically say that a graph is sparse whenever $|E| \in O(|V|)$ - i.e there are few enough edges. Similarly, we say that a graph is dense whenever $|E| \in \Theta(|V|^2)$ - i.e there are many edges in your graph. These are not really rules, but rather just the terminology one often uses in textbooks.

An adjacency matrix requires $\Theta(|V|^2)$ space to store, while an adjacency list requires $\Theta(|V| + |E|)$ space to store. So when the graph is sparse, using an adjacency matrix is wasteful in terms of space usage, even though answering queries may be faster. On the other hand, is the graph is dense, then both representations require a quadratic amount of space to store, and so you are better off using the adjacency matrix for $O(1)$ edge queries. There are other trade-offs that one can consider as well depending on the queries you anticipate using often, such as vertex insertion/deletion, neighborhood queries, among others... but this is the general rule of thumb.

It may also make a difference when implementing certain algorithms, like Dijkstra's. Using an adjacency matrix, the algorithm takes $O(|V|^2)$ time, but using an adjacency list, it can be implemented in $O(|V| + |E| \log |E|)$ time. This type of trade-off is common when implementing different graph algorithms.