The adjacency matrix is a square matrix that’s used to represent a graph. The elements that are next to each other represent adjacent vertices. Why would you want to create an adjacency matrix? To save time. The adjacency matrix is much more efficient when trying to figure out the adjacent nodes in a graph. Let’s look at an example of how someone would create an adjacency matrix from a directed graph.

Although the graph looks complicated, creating an adjacency matrix is a simple process. Since there are 6 vertices, the adjacency matrix will have 6 rows and 6 columns. Each entry is initially filled with zeros.

Starting at vertex 1, there is one outbound edge to vertex 6. So, the first entry in the adjacency matrix is at row 1, column 6. We change the 0 to 1 to indicate that there is an edge from vertex 1 to vertex 6.

Next, we look at vertex 2. Vertex 2 has two outbound edges: one outbound edge to 1, and another outbound edge to 5. We’ll update the adjacency matrix by adding a 1 for entry (2,1) and entry (2,5).

Vertex 3 has two outbound edges: one outbound edge leads to vertex 2, and the other outbound edge goes to vertex 5. We update the matrix entries (3,2) and (3,5).

Vertex 4 has one outbound edge to vertex 6, so we update entry (4,6).

We move to vertex 5, which has 4 outbound edges. Entries (5,1), (5,3), (5,4), and (5,6) are updated. Make sure to reference the graph above to verify this data yourself.

Finally, we examine vertex 6. Vertex 6 has 3 outbound edges.

Entries (6,1), (6,2), and (6,5) are updated in the adjacency matrix. This completes the creation of the adjacency matrix.

The adjacency matrix is a tool that you can use if you’re trying to figure out whether the graph is symmetric. If we look at each entry, Axy, and compare it to Ayx, we can conclude that this graph is not symmetric. A symmetric graph would have Axy = Ayx for each entry. For example, entry (2,1) has a value of 1, while entry (1,2) has a value of 0.

If you look at the diagonal, you can quickly tell that this graph has no self-loops. If there were any self-loops (a vertex with an edge pointing to itself), the diagonal entry for that vertex would show a 1.

To find the adjacent vertices for some vertex, you just have to scan that particular row and see if there are any non-zero entries. For vertex 5 the adjacent vertices are 1, 3, 4, and 6.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Graph Representation and many more.