Graph Representation

Graph Declaration

First let us look at the components of graph data structure. To represent graphs, we need the number of vertices, the number of edges and also their interconnections.

Adjacency Matrix

The adjacency matrix of a graph is a square matrix of size N × N, where N is the number of Nodes of the graph. It is basically a Boolean matrix which is initialized with zero. Let’s Say our adjacency matrix as Adj[][]. So Adj[u][v] is set to 1 if there is an edge between node u and v, otherwise it is zero.

Now if the graph is undirected you can either set Adj[v][u] = 1, whenever you set Adj[u][v] = 1 or you can just leave Adj[v][u] = 0. In both the cases to save time we will just process Diagonally half of this Matrix.

Now if the graph is directed you have to consider Adj[v][u] whenever you set Adj[u][v] to 1, because Adj[v][u] ≠ Adj[u][v] for directed graph. But in that case also we will just process diagonal half of the matrix as in each step when Adj[u][v] comes we will also check Adj[v][u].

The Adjacency matrix representation is good if the graphs are dense. The matrix requires O(N²) bits of Storage and O(N²) time for Initialization. If the number of edges is proportional to N²,then there is no problem because N²steps are required to read the edges.

But the Downside is that it doesn’t matter the edges are minimum or maximum it will always take same amount of Space and Time. Which is why Nowadays we don’t use this kind of implementation. If N ≤ 10⁴, we can use It, but if N ˃ 10⁴ We can’t use this implementation in competitive coding platforms. It will give TLE error.

Adjacency List

Adjacency list is better implementation. The basic concept is that we create a list of node and each list node have only those nodes which are connected to the list node.

See below Images to get better idea.

One thing to be kept in mind is that the order of edges in input is important. This is because the order in which edges appear on the adjacency list affects the order in which they are processed by algorithms.

The adjacency List takes O(N+M) of space where N is number of node and M are number of edges. Which is far more less than Adjacency matrix. Also graph traversals are fast & easier in Adjacency List. 

Go to the Implementation Part to Know how They are Implemented.

More Topics will be Added Soon 💚