Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Representation of Graphs
2.1.
Adjacency Matrix
2.2.
Incidence Matrix
2.3.
Adjacency List
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Graph Representations

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A graph is a non-linear data structure that depicts relationships among the entities. Every graph is a set of points referred to as nodes or vertices, which are connected using edges. The vertices here represent entities in a graph. On the other hand, edges express relationships between entities. 

 

Graphs can broadly be categorized into Undirected or Directed. 

An undirected graph with five vertices is illustrated below.

 

 

Representation of Graphs

A graph can be represented using an adjacency matrix and an adjacency list.

There are also other representations like Incidence Matrix and Incidence List, which we will see further in this article. The choice of graph representation is situation-specific. It depends on the type of operations and ease of use.

Checkout also: Application of graph data structure

Adjacency Matrix

Adjacency Matrix is a 2D array of size V x V where V represents the number of vertices in a graph. Let the 2D array be adj[][], in that adj[i][j] = 1 indicates that there is an edge going from vertex i to vertex j.

Adjacency Matrix is also used to represent weighted graphs. 

Must Read Difference between ArrayList and LinkedList

 

Example:

Consider the following undirected graph representation:

 

 

Directed graph represenation

 

 

Pros: In adjacency, matrix representation is easier to implement and follow.

 

Cons: A lot of space and time is invested in visiting all the neighbors of a vertex, and we have to traverse all the vertices in the graph.

Incidence Matrix

The incidence matrix A of an undirected graph has a row for each vertex and a column for each graph's edge. The element A[[i,j]] of A is '1' if the ith vertex is a vertex of the jth edge and '0' otherwise.

The incidence matrix A of a directed graph has a row for each vertex and a column for each graph's edge. The element A[[i,j] of A is '− 1' if the ith vertex is an initial vertex of the jth edge, '1' if the ith vertex is a terminal vertex; otherwise, it will be '0'.

 

This incidence matrix is filled with either 0 or 1 or -1. Where,

  • 0 is used to represent a row edge that is not connected to a column vertex.
  • 1 is used to represent a row edge connected as the outgoing edge to a column vertex.
  • -1 is used to represent a row edge connected as an incoming edge to a column vertex.

 

Example for directed graph representation.

 

 

Adjacency List

 

In the adjacency list representation of a graph, every vertex is represented as a node. The node may either contain a reference or data to a linked list. This linked list will provide us with a list of all adjacent nodes to the current node.

 

Example

Adjacency list for the undirected graph.

 

 

List corresponding to node ‘3’ is the maximum having four entries.

 

Pros: Adjacency list enables a faster search process in comparison to adjacency matrix.

Adjacency list saves a lot of space.

 

Cons: It is not the best representation of graphs especially when it comes to adding or removing nodes.
Check out this problem - No of Spanning Trees in a Graph

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

1. What do you mean by a graph?

A graph is a data structure that is used to depict the relationships among the entities with the help of vertex and edges.

 

2. What is the best data structure to represent a graph?

There isn’t one. It all depends on what you want to do with the graph and the properties of the graph itself. Adjacency matrices are pretty good for dense, directed graphs. They’re very compact with only one bit per edge. For sparse graphs, it is usual to either have an adjacency list per node, or to store just the edges in a lookup structure such as a hash table.

Key Takeaways

This blog has extensively shown the various ways of representing the graph Data Structure. The best out of the Adjacency matrix, Adjacency list and Incidence matrix depend on what you want to do with the graph. 

Related Article:

 

If you want to prepare for the graph algorithms look at this amazingly written article for the best guidance towards the same.

 

Also check out the top interview questions based on the graph data structure.

 

Happy Coding!!!

 

 

Previous article
Graph Types and Applications
Next article
Euler and Hamilton paths
Live masterclass