As you can imagine, writing down all the pairs of connected nodes (that is, those that have edges between them) to keep track of the relationships in a graph can get tedious, especially as graphs can get very large. For this reason, we use what is known as the adjacency matrix, which is the fundamental mathematical representation of a graph.
Let's suppose we have a graph with n nodes, each of which has a unique integer label (
) so that we can refer to it easily and without any ambiguity whatsoever. For the sake of simplicity, in this example, n = 6. Then, this graph's corresponding adjacency matrix is as follows:
Let's take a look at the matrix for a moment and see why it is the way it is. The first thing that immediately pops out is that the matrix has a size of 6 × 6 (or n × n) because size is important to us. Next, we notice that...