Adjacency matrix meaning and definition in DSA

Last Updated : 05 Oct, 2024

An adjacency matrix is a square matrix of N x N size where N is the number of nodes in the graph and it is used to represent the connections between the edges of a graph.

Graph representation of undirected graph to Adjacency Matrix

Directed_to_Adjacency_matrix

Graph representation of directed graph to Adjacency Matrix

Characteristics of the adjacency matrix are:

The size of the matrix is determined by the number of vertices (or nodes) in a graph.
The edges in the graph are represented as values in the matrix. In case of unweighted graphs, the values are 0 or 1. In case of weighted graphs, the values are weights of the edges if edges are present, else 0.
If the graph has few edges, the matrix will be sparse.

How to build an Adjacency Matrix:

It is very easy and simple to construct an adjacency matrix for a graph there are certain steps given below that you need to follow:

Create an n x n matrix where n is the number of vertices in the graph.
Initialize all elements to 0.
For each edge (u, v) in the graph, if the graph is undirected mark a[u][v] and a[v][u] as 1, and if the edge is directed from u to v, mark a[u][v] as the 1. (Cells are filled with edge weight if the graph is weighted)

Applications of the Adjacency Matrix:

Graph algorithms: Many graph algorithms like Floyd-Warshall algorithm
Image processing: Adjacency matrices are used in image processing to represent the adjacency relationship between pixels in an image.
Finding the shortest path between two nodes: By performing matrix multiplication on the adjacency matrix, one can find the shortest path between any two nodes in a graph.

Advantages of using Adjacency Matrix:

An adjacency matrix is simple and easy to understand.
Adding or removing edges from a graph is quick and easy.
It allows constant time access to any edge in the graph.

Disadvantages of using Adjacency Matrix:

It is inefficient in terms of space utilisation for sparse graphs because it takes up O(N²) space.
Computing all neighbors of a vertex takes O(N) time.

What else can you read?

Connected component definition & meaning in DSA

zaidkhan15

News

Improve

Article Tags :

Practice Tags :

Graph

Similar Reads

Adjacency matrix meaning and definition in DSA

An adjacency matrix is a square matrix of N x N size where N is the number of nodes in the graph and it is used to represent the connections between the edges of a graph. Characteristics of the adjacency matrix are:The size of the matrix is determined by the number of vertices (or nodes) in a graph.

Connected component definition & meaning in DSA

Connected component in an undirected graph refers to a group of vertices that are connected to each other through edges, but not connected to other vertices outside the group. For example in the graph shown below, {0, 1, 2} form a connected component and {3, 4} form another connected component. Char

Disjoint Set meaning and definition in DSA

Disjoint Set is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets and it is used to efficiently solve problems that involve grouping elements into sets and performing operations on them. Characteristics of the Disjoint Set:It keeps a set partitioned

Graph definition & meaning in DSA

A Graph is a non-linear data structure consisting of vertices and edges where two vertices are connected by an edge. Properties of a Graph:Vertices (nodes): The points where edges meet in a graph are known as vertices or nodes. A vertex can represent a physical object, concept, or abstract entity.Ed

Implementation of DFS using adjacency matrix

Depth First Search (DFS) has been discussed in this article which uses adjacency list for the graph representation. In this article, adjacency matrix will be used to represent the graph.Adjacency matrix representation: In adjacency matrix representation of a graph, the matrix mat[][] of size n*n (wh

Singly Linked List definition & meaning DSA

A singly linked list is a special type of linked list in which each node has only one link that points to the next node in the linked list. Characteristics of a Singly Linked List:Each node holds a single value and a reference to the next node in the list.The list has a head, which is a reference to

Graph Representation using Adjacency Matrix in C

A graph is a data structure having a set of vertices and a collection of edges that each connect a pair of vertices. There are several ways to represent a graph in computer memory, and one of them is using an adjacency matrix. An adjacency matrix is a 2D array with one row per vertex and one column

Implementation of BFS using adjacency matrix

Breadth First Search (BFS) has been discussed in this article which uses adjacency list for the graph representation. In this article, adjacency matrix will be used to represent the graph. Adjacency matrix representation: In adjacency matrix representation of a graph, the matrix mat[][] of size n*n

Graph Adjacency Matrix in Java

A graph is a type of data structure used to represent the relationship between the entities. In this article, we will learn to represent a graph in the form of Adjacency Matrix. Graph Adjacency MatrixThe Adjacency matrix is the way to represent the graphs using the 2D array. It is the fundamental da

Add and Remove Edge in Adjacency Matrix representation of a Graph

Prerequisites: Graph and its representationsGiven an adjacency matrix g[][] of a graph consisting of N vertices, the task is to modify the matrix after insertion of all edges[] and removal of edge between vertices (X, Y). In an adjacency matrix, if an edge exists between vertices i and j of the grap

Adjacency Matrix in Python

Given the edges of a graph as a list of tuples, construct an adjacency matrix to represent the graph in Python. Examples: Input:V = 3 (Number of vertices)edges = [(0, 1), (1, 2), (2, 0)] Output: [ [0, 1, 1], [1, 0, 1], [1, 1, 0]] Input:V = 4 (Number of vertices)edges = [(0, 1), (1, 2), (1, 3), (2, 3

Adjacency Matrix of Directed Graph

Adjacency Matrix of a Directed Graph is a square matrix that represents the graph in a matrix form. In a directed graph, the edges have a direction associated with them, meaning the adjacency matrix will not necessarily be symmetric. In a directed graph, the edges have a direction associated with th

Convert Adjacency Matrix to Adjacency List representation of Graph

Prerequisite: Graph and its representations Given a adjacency matrix representation of a Graph. The task is to convert the given Adjacency Matrix to Adjacency List representation. Examples: Input: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ] Output: The adjacency list is: 0 -> 2 1 -> 2 2 -

Add and Remove vertex in Adjacency Matrix representation of Graph

A graph is a presentation of a set of entities where some pairs of entities are linked by a connection. Interconnected entities are represented by points referred to as vertices, and the connections between the vertices are termed as edges. Formally, a graph is a pair of sets (V, E), where V is a co

Comparison between Adjacency List and Adjacency Matrix representation of Graph

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. In this article, we will understand the difference between the ways of representation of the graph. A gr

Adjacency Matrix Representation

Adjacency Matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. An adjacency matrix is a simple and straightforward way to represent graphs and is particularly useful for dense graphs. Table of Cont

Adjacency List Generation from Edge Connections

Given a list of undirected edge connections of size E, create an adjacency list for a graph with V nodes and E edges following 0-based indexing and return the adjacency list. Examples: Input: V = 4, E = 5, edges = [[0, 1], [1, 2], [2, 3], [0, 2], [1, 3]]Output: [[1, 2], [0, 2, 3], [1, 3, 0], [2, 1]]

Prim’s MST for Adjacency List Representation | Greedy Algo-6

We recommend reading the following two posts as a prerequisite to this post. Greedy Algorithms | Set 5 (Prim’s Minimum Spanning Tree (MST)) Graph and its representationsWe have discussed Prim's algorithm and its implementation for adjacency matrix representation of graphs. The time complexity for th

Add and Remove Edge in Adjacency List representation of a Graph

Prerequisites: Graph and Its RepresentationIn this article, adding and removing edge is discussed in a given adjacency list representation. A vector has been used to implement the graph using adjacency list representation. It is used to store the adjacency lists of all the vertices. The vertex numbe

翻译：