Do you think IIT Guwahati certified course can help you in your career?
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.
What is 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.
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.
Consider the following undirected graph representation:
Directed graph representation
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
Frequently Asked Questions
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.
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.
Conclusion
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.
85+ registered