In this tutorial, you will learn what an adjacency matrix is. Likewise, you will discover working instances of adjacency matrix in C, C++, Java, and Python.
An adjacency matrix is a method of addressing a graph G = {V, E} as a matrix of booleans.
In this article, you will learn-
What is an adjacency matrix?
An adjacency matrix is a two-dimensional matrix used to map the relationship between the nodes of a graph. A graph is a set of vertices (nodes) associated with edges.
In an adjacency matrix, 0 implies that no relationship between nodes exists and 1 implies that a relationship between nodes exists.
Adjacency matrix representation
The size of the matrix is VxV where V is the number of vertices in the graph and the value of a section Aij is either 1 or 0 relying upon whether there is an edge from vertex I to vertex j.
Example
The picture beneath shows a graph and its comparable adjacency matrix.
In the event of undirected graphs, the matrix is symmetric about the diagonal in view of each edge (i,j), there is additionally an edge (j,i).
Pros of the adjacency matrix
The fundamental activities like adding an edge, eliminating an edge and checking whether there is an edge from vertex I to vertex j are amazingly time effective, steady time tasks.
In the event that the graph is thick and the quantity of edges is huge, adjacency matrix ought to be the best option. Even if the graph and the adjacency matrix is sparse, we can address it using data structures for sparse matrices.
The biggest advantage however comes from the use of matrices. The new advances in equipment enable us to perform even costly matrix procedure on the GPU.
By performing procedures on the adjacent matrix, we can get significant experiences into the idea of the graph and the connection between its vertices.
Cons of the adjacency matrix
Graphs out in the wild typically don’t have an excessive number of associations and this is the significant motivation behind why adjacency lists are the better decision for most errands.
While fundamental activities are simple, tasks like inEdges and outEdges are costly when using the adjacency matrix representation.
Python, Java, and C/C++ Examples
In the event that you know how to create two-dimensional arrays, you additionally know how to create an adjacency matrix.
Python
# Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = [] for i in range(size): self.adjMatrix.append([0 for i in range(size)]) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix[v1][v2] = 1 self.adjMatrix[v2][v1] = 1 # Remove edges def remove_edge(self, v1, v2): if self.adjMatrix[v1][v2] == 0: print("No edge between %d and %d" % (v1, v2)) return self.adjMatrix[v1][v2] = 0 self.adjMatrix[v2][v1] = 0 def __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('{:4}'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main()
Java
// Adjacency Matrix representation in Java public class Graph { private boolean adjMatrix[][]; private int numVertices; // Initialize the matrix public Graph(int numVertices) { this.numVertices = numVertices; adjMatrix = new boolean[numVertices][numVertices]; } // Add edges public void addEdge(int i, int j) { adjMatrix[i][j] = true; adjMatrix[j][i] = true; } // Remove edges public void removeEdge(int i, int j) { adjMatrix[i][j] = false; adjMatrix[j][i] = false; } // Print the matrix public String toString() { StringBuilder s = new StringBuilder(); for (int i = 0; i < numVertices; i++) { s.append(i + ": "); for (boolean j : adjMatrix[i]) { s.append((j ? 1 : 0) + " "); } s.append("\n"); } return s.toString(); } public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); System.out.print(g.toString()); } }
C
// Adjacency Matrix representation in C #include <stdio.h> #define V 4 // Initialize the matrix to zero void init(int arr[][V]) { int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr[i][j] = 0; } // Add edges void addEdge(int arr[][V], int i, int j) { arr[i][j] = 1; arr[j][i] = 1; } // Print the matrix void printAdjMatrix(int arr[][V]) { int i, j; for (i = 0; i < V; i++) { printf("%d: ", i); for (j = 0; j < V; j++) { printf("%d ", arr[i][j]); } printf("\n"); } } int main() { int adjMatrix[V][V]; init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; }
C++
// Adjacency Matrix representation in C++ #include <iostream> using namespace std; class Graph { private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero Graph(int numVertices) { this->numVertices = numVertices; adjMatrix = new bool*[numVertices]; for (int i = 0; i < numVertices; i++) { adjMatrix[i] = new bool[numVertices]; for (int j = 0; j < numVertices; j++) adjMatrix[i][j] = false; } } // Add edges void addEdge(int i, int j) { adjMatrix[i][j] = true; adjMatrix[j][i] = true; } // Remove edges void removeEdge(int i, int j) { adjMatrix[i][j] = false; adjMatrix[j][i] = false; } // Print the martix void toString() { for (int i = 0; i < numVertices; i++) { cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix[i][j] << " "; cout << "\n"; } } ~Graph() { for (int i = 0; i < numVertices; i++) delete[] adjMatrix[i]; delete[] adjMatrix; } }; int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.toString(); }
Adjacency Matrix Applications
- Creating routing table in networks
- Navigation tasks
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.