Adjacency Matrix is a way of representing a graph G = {V, E} as a Boolean matrix.
Representation of adjacency matrix
The size of the matrix is VxV, where V is the number of vertices in the graph, and the value of the entry Aij is 1 or 0, depending on whether there is an edge from vertex i to vertex j.
Example of adjacency matrix
The image below shows the graph and its equivalent adjacency matrix.
In the case of an undirected graph, the matrix is diagonally symmetric because each edge (i, j) also has an edge (j, i).
Advantages of adjacency matrix
Basic operations such as adding an edge, removing an edge, and checking for an edge from vertex i to vertex j are extremely time-efficient operations. Operations with constant time.
If the graph is dense and the number of edges is large, the adjacency matrix should be the first choice. Even if the graph and adjacency matrix are sparse, we can represent it using sparse matrix data structures.
However, the biggest benefit comes from the use of matrices. Recent advances in hardware allow us to perform even expensive matrix operations on the graphics processing unit (GPU).
By performing operations on an adjacent matrix, we can obtain important information about the nature of the graph and the relationship between its vertices.
Cons of adjacency matrix
Due to the space requirement of the VxV adjacency matrix, there may not be enough memory. But usually graphs don't have too many connections, and this is the main reason why adjacency lists are the best choice for most problems.
Although the basic operations are simple, operations such as inEdges and outEdges are expensive when using adjacency matrix representation.
Adjacency matrix code
If you know how to create two-dimensional arrays, then you also know how to create an adjacency matrix.
Adjacency matrix in C++
#include <iostream>
using namespace std;
class Graph {
private:
bool** adjMatrix;
int numVertices;
public:
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;
}
}
void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
void removeEdge(int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
bool isEdge(int i, int j) {
return adjMatrix[i][j];
}
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();
/* Outputs
0: 0 1 1 0
1: 1 0 1 0
2: 1 1 0 1
3: 0 0 1 0
*/
}
Java adjacency matrix
public class Graph {
private boolean adjMatrix[][];
private int numVertices;
public Graph(int numVertices) {
this.numVertices = numVertices;
adjMatrix = new boolean[numVertices][numVertices];
}
public void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
public void removeEdge(int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
public boolean isEdge(int i, int j) {
return adjMatrix[i][j];
}
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());
/* Outputs
0: 0 1 1 0
1: 1 0 1 0
2: 1 1 0 1
3: 0 0 1 0
*/
}
}
Adjacency Matrix in Python
class Graph(object):
def __init__(self, size):
self.adjMatrix = []
for i in range(size):
self.adjMatrix.append([0 for i in range(size)])
self.size = size
def addEdge(self, v1, v2):
if v1 == v2:
print("Same vertex %d and %d" % (v1, v2))
self.adjMatrix[v1][v2] = 1
self.adjMatrix[v2][v1] = 1
def removeEdge(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 containsEdge(self, v1, v2):
return True if self.adjMatrix[v1][v2] > 0 else False
def __len__(self):
return self.size
def toString(self):
for row in self.adjMatrix:
for val in row:
print('{:4}'.format(val)),
print
def main():
g = Graph(5)
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.toString()
if __name__ == '__main__':
main()
