GCSE Link: None
Here's Diagram 1 again from the previous page.
Diagram 1
To implement a graph, we need to store which nodes are adjacent to each other, i.e. which nodes have an edge connecting them. There are two options to choose from when implementing a graph:
An adjacency list offers a memory-efficient way of storing adjacent nodes.
Here's what the adjacency list for the graph in Diagram 1 would look like:
{
"A": ["B", "C", "D", "G"],
"B": ["A", "E"],
"C": ["A", "G"],
"D": ["A", "F"],
"E": ["B", "F", "H"],
"F": ["D", "E", "G"],
"G": ["A", "C", "F"],
"H": ["E"],
}
Note that it is called an adjacency list, but is implemented as a dictionary. The size of this
dictionary is N + E, where N is the number of nodes, and E is the
number of edges.
An adjacency matrix is an alternative way of storing adjacent nodes.
Here's what the adjacency matrix for the graph in Diagram 1 would look like:
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| A | - | 1 |
1 |
1 |
0 |
0 |
1 |
0 |
| B | 1 |
- | 0 |
0 |
1 |
0 |
0 |
0 |
| C | 1 |
0 |
- | 0 |
0 |
0 |
1 |
0 |
| D | 1 |
0 |
0 |
- | 0 |
1 |
0 |
0 |
| E | 0 |
1 |
0 |
0 |
- | 1 |
0 |
1 |
| F | 0 |
0 |
0 |
1 |
1 |
- | 1 |
0 |
| G | 1 |
0 |
1 |
0 |
0 |
1 |
- | 0 |
| H | 0 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
It can be implemented as a 2D array of booleans. The size of this array is
N2, where N is the number of nodes.
What is the main advantage of using an adjacency matrix over an adjacency list?
It is a lot faster to check if there is a node between two edges with an adjacency matrix, as you only have to get the item at the correct indices. (With an adjacency list, you would have to check if the list contains the second node, which gets slower and slower for larger graphs).