 Loading, please wait...  # Briefly explain Adjacency Matrix and Adjacency List in Data Structures | Data Structure Tutorial

## 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.

• 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.

• 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.

• Creating a routing table in networks

## 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.