Adjacency Matrix¶
To represent a graph with n vertices, we can use an n×n matrix where rows and columns correspond to vertices. The entry in row i and column j is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. For example, the adjacency matrix for the following simple undirected graph:
is:
In simple graphs (without loops), the diagonal entries of the adjacency matrix are always zero.
Sample code for creating an adjacency matrix:
1# Creating adjacency matrix
2n = 4 # Number of vertices
3adjacency_matrix = [[0 for _ in range(n)] for _ in range(n)]
4
5edges = [(0, 1), (0, 3), (1, 2), (1, 3)] # Graph edges
6
7for i, j in edges:
8 # If there is an edge between i and j
9 adjacency_matrix[i][j] = 1
10 adjacency_matrix[j][i] = 1 # For undirected graphs
11
12# Prints the adjacency matrix
13for row in adjacency_matrix:
14 print(row)
Adjacency Matrix¶
The adjacency matrix is an n × n matrix used to represent simple graphs. In this matrix, \(a_{ij}\) represents the number of edges between vertex i and vertex j in the graph. If you note, this matrix is symmetric. The entries of this matrix are zero and one.
In graphs with multiple edges and loops¶
In these graphs, the adjacency matrix is used with its original definition, with the difference that the entries are no longer necessarily zero or one and can take any numerical value.
In directed graphs, the adjacency matrix is defined such that \(a_{ij}\) represents the number of edges going from vertex i to vertex j.
A final note regarding the adjacency matrix is that it is not used when the graph is weighted, though a matrix similar to this matrix is employed for finding shortest paths. In all the definitions above, edges are assumed to be unweighted.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
