Introduction to Sparse Matrix in Data Structure4 min read

In this article, we will learn about Sparse matrix, its use and its different representation.

What is a sparse matrix?

A matrix can be defined with a 2-dimensional array with column m and row n represented as m * n matrix. However, there may be a matrix or matrices that may contain less Non-Zero values than Zero values. Such a matrix is known as the Sparse matrix.

We can say that it is a matrix that contains a few Non-Zero elements.

Why use Sparse Matrix instead of a simple matrix?

There are mainly two reasons:

  1. Storage: Sparse matrix allows us to use the memory to store only non-zero elements. So, less storage is required.
  2. Computing time: designing a data- structure that traverses only Non-Zero elements, computing time can be saved.

Sparse Matrix Representation:

There are two ways to represent a sparse matrix:

  1. Triplet Representation(Array Representation)
  2. Linked Representation

1. Triplet Representation(Array Representation)

It is an array representation where only Non-Zero elements are store in three rows named as:

  • Row: This contains an index number for a row where non-zero elements are situated.
  • Column: This contains an index number for a column where the non-zero element is stored.
  • Value: These contain all the values of Non-Zero elements located at their respective index i.e. rows and columns.
Sparse matrix

In the above diagram of matrix size 5* 6, there are 5 non-zero elements (8, 7, 5, 3, 1). The right-hand side table indicates it’s a sparse matrix with Rows, Columns, and Values. Values are the non-zero elements that are present in their particular row and column. Eg. 0th row and 2nd column contain the non-zero element 8 in the sparse matrix. Ans the following shows a similar pattern.

Triplet Representation(Array Representation) using C++

Output of sparse matrix using C++:


2. Linked List Representation:

The Linked list data structure is used to represent a sparse matrix.

Here, each node has four fields and they are:

  • Row: This contains an index number for a row where non-zero elements are situated.
  • Column: This contains an index number for a column where a non-zero element is stored.
  • Value: These contain all the values of Non-Zero elements located at their respective index i.e. rows and columns.
  • Next Node: This contains the address of the next node.

C Program to determine if a given matrix is in a sparse matrix or not.

Output of sparse matrix using C:


MORE

C++ Structures

In the C/C++ programming language, the structure is user-defined data types that allow us to store the combination of different data types together. All the …
Read More

C++ Static Keyword

Static s a keyword in C++ that is when used with different types gives different meanings. static keyword can be used with variables in a …
Read More

C++ Templates

Templates in C++ are the powerful feature that allows us to write generic programs (generic classes and generic functions). A single class or function is …
Read More

C++ Friend Function

There are private and protected members in a class that is inaccessible from outside of the class, constituting one of the concepts of object-oriented programming …
Read More

this Pointer in C++

In C++, this is a keyword that refers to the current instance of a class and this pointer holds the address or points to the …
Read More

Inheritance in C++

Inheritance is one of the most important concepts of object-oriented programming. In C++, inheritance is the process of deriving the properties and behaviors of one …
Read More