Graph Representation in Data Structure
We can implement a graph in a computer program in two ways, these are:
1. Sequential Representation
2. Linked Representation
Sequential Representation:
In sequential representation we use a 2D array of order nxn where n is the total number of vertices in the graph. It is a simple way to represent a graph in memory. A graph with n nodes takes n2 space to represent it sequentially in memory and also takes O(n2) time to perform the graph operations and It is used to solve the graph problems.
Adjacency Matrix:
Suppose G is a graph with n nodes and suppose the vertices of graph G are ordered are called 1, 2, 3,.., n. Then the adjacency matrix A of the graph G is an nxn matrix defined as follows:
A[i][j]=1 // if there is an edge from node i to node j
=0 // otherwise
Such a matrix that contains only 1 or 0 is called a bit matrix or Boolean matrix. The adjacency matrix of an undirected simple graph is a Symmetric matrix. In the adjacency matrix of an undirected simple graph, the number of 1 is twice the number of edges in the graph.
Path Matrix:
Suppose G is a directed graph with n nodes and suppose the vertices of graph G are ordered called 1, 2, 3,.., n. Then the path matrix P of the graph G is an nxn matrix defined as follows:
P[i][j]=1 // if there is a path from vertex i to vertex j
=0 // otherwise
Weighted Matrix:
The weighted matrix W of a weighted graph G with n nodes is an nxn matrix which can be defined as:
W[i][j]=weight of the edge
=∞ (large value) // otherwise
Linked Representation:
In the adjacency matrix, it is difficult to insert new nodes or edges in the graph. First of all the time complexity for the insertion or deletion of new nodes or edges in the adjacency matrix is high. Moreover, the array is static. In the linked representation of the graph, we will maintain two lists. The first list will keep track of all the nodes in the graph and the second list will maintain a list of adjacent nodes for each node to keep the track of the edges.
