Advantages and Disadvantages of Adjacency Matrix Graph Representation

What is Adjacency Matrix Graph Representation?

Adjacency Matrix is a graph data structure. It is a technique to store graphs. The adjacency matrix is a 2D boolean array of size V² where V is the number of vertices in the graph.

The adjacency matrix contains V rows and V columns. The i-th row and j-th column of the adjacency matrix tell us if there is an edge from i-th vertex to j-th vertex.

For example, suppose the following is the adjacency matrix for a graph with 5 vertices.

The graph for the corresponding adjacency matrix is

If the graph is weighted then the adjacency matrix stores weight of edges instead of a boolean value.

Advantages of Adjacency Matrix Representation

1. We can determine if two vertices are adjacent to each other in constant time.
2. We can add an edge in the graph in constant time.
3. We can delete an edge form the graph in constant time.

Disadvantages of Adjacency Matrix Representation

1. The size of adjacency matrix is V². Suppose there is a graph with 1000 vertices and 1 edge. We are using an array of size 1000² for storing one edge which is a waste of memory.
2. Traversing the graph using algorithms like DPS/BFS requires O(V²) time in case of adjacency matrix whereas we can traverse the graph in O(V+E) time using adjacency list.

When to use Adjacency Matrix?

1. If the graph contains edges in order of V², then it is better to use adjacency matrix as compared to adjacency list. This is because the size of both adjacency list and adjacency matrix will be comparable so using adjacecny matrix doesn’t necceessary waste a lot of memeory.
2. If we want to perform operations like add/delete or check that the vertices are adjancent or not very frequently, then it is recommended to use adjacency matrix since we can perform these operations in constant time.