Briefly explain Adjacency Matrix and Adjacency List in Data Structures | Data Structure Tutorial

Adjacency Matrix and Adjacency List in Data Structures

In this article, you will learn about the advantages and disadvantages of the Adjacency Matrix and Adjacency List.

What is Adjacency Matrix in Data Structures?

An adjacency matrix is a way of representing a graph in the form of a matrix using values 0’s and 1’s. A finite graph can be represented in the matrix form on a computer, where the 0’s and 1’s values of the matrix indicate if there is any direct path between two vertices. 

Pros of Adjacency Matrix

• The fundamental operations like adding an edge, deleting an edge, and checking whether there is an edge from vertex i to vertex j are completely time efficient, constant time operations.
• If the graph is dense and the edge is high, an adjacency matrix should always be the first choice. Even if the graph and the adjacency matrix are scattered, we can represent them with the help of data structures for sparse matrices.
• The huge advantage comes from the use of matrices. The recent advances in hardware enable us to perform even the expensive matrix operations on the GPU.
• By executing operations on the adjacent matrix, we can get essential information into the nature of the graph and the relationship between its vertices.

Cons of Adjacency Matrix

• The vertex-to-vertex space requirement of the adjacency matrix makes it a memory hog. Graphs don’t have too many connections and this is a huge reason why adjacency lists are a good choice for most tasks.
• The basic operations are easy, but operations like inEdges and outEdges are extremely expensive when using the adjacency matrix representation.

Applications of Adjacency Matrix

• Creating a routing table in networks
• Navigation Tasks application

What is an Adjacency List in Data Structures?

An adjacency list represents a graph in the form of an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the different vertices that form an edge with the vertex.

Pros of Adjacency List

• An adjacency list is very efficient in terms of memory because we only need to store the values of the edges. For a sparse graph with millions of vertices and edges, this can have a huge saved space.
• It helps in finding all the vertices adjacent to a vertex easily.

Cons of Adjacency List

• Finding the adjacent list is not quicker than the adjacency matrix because all the nodes which are connected must be explored to figure them out.