# Graph Representation in Data Structure

We can implement a graph in a computer program in two ways, these are:
1. Sequential 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.

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 // if there is an edge from i to j
= (large value) // otherwise