The Self-Taught Computer Scientist

Figure 16.8: A graph with four vertices

---

Chapter 16 Graphs
177
One problem with adjacency matrices is sparsity or empty cells. There are eight empty cells in this 
example. Adjacency matrices are not a very efficient way to store data because they can end up with 
a large number of empty cells, which is an inefficient use of your computer’s memory.
Finally, you can also represent a graph with an adjacency list. An adjacency list is a collection of 
unordered lists, with each list representing the connections for a single vertex. Here is the same graph 
from Figure 16.8 as an adjacency list:
{
10: [20, 30],
20: [10, 30],
30: [10, 20, 40],
40: [30]
}
As you can see, the node 10 connects to 20 and 30, the node 20 connects to 10 and 30, and so on.
When to Use Graphs
As you already know, there are many different graph implementations. Adding a vertex and an edge 
to a graph is generally O(1). The run time for searching, deleting, and other algorithms in a graph 
depends on the graph’s implementation and which data structures you used to implement the graph: 
arrays, linked lists, hash tables, etc. In general, the performance of basic operations on graphs depends 
on either the number of vertices in the graph, the number of edges in the graph, or some combination 
of those two numbers since graphs essentially deal with two things: items in the graph (vertices) and 
connections (edges) between those items.
Graphs are helpful in many situations. For example, software engineers at social media companies 
like Instagram and Twitter use vertices in a graph to represent people and edges to represent the asso-
ciations between them. Programmers also use graphs to build networks, often representing the devices 
on it as vertices with the edges representing wireless or wired links between those devices. You can 
0
1
1
0
10
20
30
40
1
0
1
0
1
1
0
1
0
10
20
30
40
0
1
0