In this tutorial, you will learn what an adjacency matrix is. Also, you will find working examples of adjacency matrix in C, C++, Java and Python.

An adjacency matrix is a way of representing a graph G = {V, E} as a matrix of booleans.

The size of the matrix is `VxV` where `V` is the number of vertices in the graph and the value of an entry `Aij` is either 1 or 0 depending on whether there is an edge from vertex i to vertex j.

The image below shows a graph and its equivalent adjacency matrix.

In case of undirected graphs, the matrix is symmetric about the diagonal because of every edge `(i,j)`, there is also an edge `(j,i)`.

The basic operations like adding an edge, removing an edge and checking whether there is an edge from vertex i to vertex j are extremely time efficient, constant time operations.

If the graph is dense and the number of edges is large, adjacency matrix should be the first choice. Even if the graph and the adjacency matrix is sparse, we can represent it using data structures for sparse matrices.

The biggest advantage however, comes from the use of matrices. The recent advances in hardware enable us to perform even expensive matrix operations on the GPU.

By performing operations on the adjacent matrix, we can get important insights into the nature of the graph and the relationship between its vertices.

The `VxV` space requirement of the adjacency matrix makes it a memory hog. Graphs out in the wild usually don't have too many connections and this is the major reason why adjacency lists are the better choice for most tasks.

While basic operations are easy, operations like `inEdges` and `outEdges` are expensive when using the adjacency matrix representation.

## Python, Java and C/C++ Examples

If you know how to create two dimensional arrays, you also know how to create an adjacency matrix.

``````# Adjacency Matrix representation in Python

class Graph(object):

# Initialize the matrix
def __init__(self, size):
for i in range(size):
self.size = size

if v1 == v2:
print("Same vertex %d and %d" % (v1, v2))

# Remove edges
def remove_edge(self, v1, v2):
print("No edge between %d and %d" % (v1, v2))
return

def __len__(self):
return self.size

# Print the matrix
def print_matrix(self):
for val in row:
print('{:4}'.format(val)),
print

def main():
g = Graph(5)

g.print_matrix()

if __name__ == '__main__':
main()``````
``````// Adjacency Matrix representation in Java

public class Graph {
private int numVertices;

// Initialize the matrix
public Graph(int numVertices) {
this.numVertices = numVertices;
}

public void addEdge(int i, int j) {
}

// Remove edges
public void removeEdge(int i, int j) {
}

// 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);

System.out.print(g.toString());
}
}``````
``````// 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;
}

void addEdge(int arr[][V], int i, int j) {
arr[i][j] = 1;
arr[j][i] = 1;
}

// Print the matrix
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() {

return 0;
}``````
``````// Adjacency Matrix representation in C++

#include <iostream>
using namespace std;

class Graph {
private:
int numVertices;

public:
// Initialize the matrix to zero
Graph(int numVertices) {
this->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++)
}
}

void addEdge(int i, int j) {
}

// Remove edges
void removeEdge(int i, int j) {
}

// 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++)
}
};

int main() {
Graph g(4);