Representation

Now you know what a graph is and when it can be used, but how you can represent it in the memory of a computer? There are two popular approaches to solve this problem, namely using an adjacency list and an adjacency matrix. Both are described in detail in the following sections.

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 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 following diagram:

The 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, the node 1 has two neighbors, namely the nodes 2 and 3, while the node 5 has four neighbors, namely the nodes 4, 6, 7, and 8. As you can see, the representation based...