Representations
At this point, you know what a graph is and when one can be used, but how can you represent one in the memory of a computer? There are two popular approaches to solve this problem, namely using an adjacency list and an adjacency matrix.
Adjacency list
The first approach requires you to extend the data of a node by specifying a list of its neighbors. Thus, you can easily get all the neighbors of a given node just by iterating through the adjacency list of a given node. Such a solution is space-efficient because you only store the data of adjacent edges. Let’s take a look at the diagram:
Figure 8.6 – Adjacency list representing an undirected and unweighted graph
This example graph contains 8 nodes and 10 edges. For each node, a list of adjacent nodes (that is, neighbors) is created, as shown on the right-hand side of the diagram. For example, node 1 has two neighbors, namely nodes 2 and 3, while node 5 has four neighbors...
