Graph and its representations

Last Updated : 02 Jan, 2024

What is Graph Data Structure?

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V, E).

Representations of Graph

Here are the two most common ways to represent a graph :

Adjacency Matrix
Adjacency List

Adjacency Matrix

An adjacency matrix is a way of representing a graph as a matrix of boolean (0’s and 1’s).

Let’s assume there are n vertices in the graph So, create a 2D matrix adjMat[n][n] having dimension n x n.

If there is an edge from vertex i to j, mark adjMat[i][j] as 1.

If there is no edge from vertex i to j, mark adjMat[i][j] as 0.

Representation of Undirected Graph to Adjacency Matrix:

The below figure shows an undirected graph. Initially, the entire Matrix is initialized to 0. If there is an edge from source to destination, we insert 1 to both cases (adjMat[destination] and adjMat[destination]) because we can go either way.

Undirected_to_Adjacency_matrix

Undirected Graph to Adjacency Matrix

Representation of Directed Graph to Adjacency Matrix:

The below figure shows a directed graph. Initially, the entire Matrix is initialized to 0. If there is an edge from source to destination, we insert 1 for that particular adjMat[destination].

Directed_to_Adjacency_matrix

Directed Graph to Adjacency Matrix

Adjacency List

An array of Lists is used to store edges between two vertices. The size of array is equal to the number of vertices (i.e, n). Each index in this array represents a specific vertex in the graph. The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i.

Let’s assume there are n vertices in the graph So, create an array of list of size n as adjList[n].

adjList[0] will have all the nodes which are connected (neighbour) to vertex 0.

adjList[1] will have all the nodes which are connected (neighbour) to vertex 1 and so on.

Representation of Undirected Graph to Adjacency list:

The below undirected graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has two neighbours (i.e, 1 and 2). So, insert vertex 1 and 2 at indices 0 of array. Similarly, For vertex 1, it has two neighbour (i.e, 2 and 0) So, insert vertices 2 and 0 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in array of list.

Graph-Representation-of-Undirected-graph-to-Adjacency-List

Undirected Graph to Adjacency list

Representation of Directed Graph to Adjacency list:

The below directed graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has two neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in array of list.

Graph-Representation-of-Directed-graph-to-Adjacency-List

Directed Graph to Adjacency list

GeeksforGeeks

Improve

Previous Article

Introduction to Graph Data Structure

Types of Graphs with Examples

Similar Reads

Sparse Matrix and its representations | Set 1 (Using Arrays and Linked Lists)

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix. Why to use Sparse Matrix instead of simple matrix ? Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store onl

Sparse Matrix and its representations | Set 2 (Using List of Lists and Dictionary of keys)

Prerequisite : Sparse Matrix and its representations Set 1 (Using Arrays and Linked Lists)In this post other two methods of sparse matrix representation are discussed. List of ListsDictionary List of Lists (LIL) One of the possible representation of sparse matrix is List of Lists (LIL). Where one list is used to represent the rows and each row cont

Graph representations using set and hash

We have introduced Graph implementation using array of vectors in Graph implementation using STL for competitive programming | Set 1. In this post, a different implementation is used which can be used to implement graphs using sets. The implementation is for adjacency list representation of graph. A set is different from a vector in two ways: it st

Maximize difference between odd and even indexed array elements by swapping unequal adjacent bits in their binary representations

Given an array arr[] consisting of N positive integers, the task is to find the maximum absolute difference between the sum of the array elements placed at even and odd indices of the array by swapping unequal adjacent bits of in the binary representation of any array element any number of times. Examples: Input: arr[] = {5, 7, 3, 1, 8}Output: 9Exp

Maximize difference between odd and even-indexed array elements by rotating their binary representations

Given an array arr[] consisting of N positive integers, the task is to find the maximum absolute difference between the sum of the array elements placed at even indices and those at odd indices of the array by rotating their binary representations any number of times. Consider only 8-bit representation. Examples: Input: arr[] = {123, 86, 234, 189}O

XOR of two numbers after making length of their binary representations equal

Given two numbers say a and b. Print their XOR after making the lengths of their binary representation equal by adding trailing zeros to the binary representation of smaller one. Examples : Input : a = 13, b = 5 Output : 7 Explanation : Binary representation of 13 is 1101 and of 5 is 101. As the length of "101" is smaller, so add a '0' to it making

Digits whose alphabetic representations are jumbled in a given string

Given a string S of length N which is the English representation of any number of digits in the range [0 - 9] in jumbled format. The task is to find the digits from this representation. Note: Print digits in any order Examples Input: S = "owoftnuoer"Output: 124Explanation: The digits here are jumbled form of one, two and four. Therefore, the requir

Check if binary representations of 0 to N are present as substrings in given binary string

Give binary string str and an integer N, the task is to check if the substrings of the string contain all binary representations of non-negative integers less than or equal to the given integer N. Examples: Input: str = “0110", N = 3 Output: True Explanation: Since substrings “0", “1", “10", and “11" can be formed from given string. Hence all binar

Find the number obtained by concatenating binary representations of all numbers up to N

Given an integer N, the task is to find the decimal value of the binary string formed by concatenating the binary representations of all numbers from 1 to N sequentially. Examples: Input: N = 12Output: 118505380540Explanation: The concatenation results in "1101110010111011110001001101010111100". The equivalent decimal value is 118505380540. Input:

Rearrange array to make decimal equivalents of reversed binary representations of array elements sorted

Given an array arr[] consisting of N positive integers, the task is to rearrange the array such that the reversed binary representation of all the array elements is sorted. If the decimal equivalent of reversed binary representations of two or more array elements is equal, then the original value is taken into consideration while rearranging the ar

Article Tags :

Practice Tags :

Graph