Graph Data Structure
Graph is a nonlinear data structure defined as a collection of vertices(nodes) and edges(links).
These nodes are connected with the help of some edges. The nodes or vertices are used to store data.
A graph is represented as G = (V, E) where,
 V is the set of vertices or nodes
 E is the set of edges in the Graph G . It is represented as ordered pairs of vertices (i,j)
Example :
Here:
V = {1, 2, 3, 4, 5}
E = {(1,2), (1,3), (1,4), (2,3), (3,4), (3,5), (4,5)}
Graph terminologies

Distance between two Vertices : It is the number of edges present between any two vertices in the shortest path. If more than one edge is used to connect two vertices, then the shortest path is considered as the distance.

Eccentricity of a Vertex : It is the maximum distance from a node or vertex to all other vertices.

Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting them.
Types of Graph
Directed and Undirected Graph
Undirected graph: A graph in which all the edges are bidirectional.
Edges do not point in any specific direction.
In an undirected graph, traversal can be done from a node_1 to node_2 or node_2 to node_1.
Total number of possible edges is
nC2
orn(n1)/2
Directed graph: A graph in which all the edges are unidirectional that is, they point in one direction only. Traversal can only be done in one direction.
the total number of possible edges is
2(nC2)
orn(n1)
Weighted and Unweighted Graph
Weighted graph: There is some weight over the edges of the graph.
Unweighted graph: There is no weight over the edges of the graph.
Connected and Disconnected Graph
Connected Graph In a connected graph from each node, there is a path to all the other nodes.
Disconnected Graph In a disconnected graph all the nodes can't be accessed from a particular node.
Graph Representation
There are two ways to represent the graph data structure:
 Adjacency matrix
 Adjacency list
Adjacency Matrix
An adjacency matrix is a 2D array of V x V vertices. Each row and column represent a vertex.
a[i][j]
= 1 – If there is an edge connecting vertex i and vertex j
a[i][j]
= 0 – If there is no edge connecting vertex i and vertex j
Total space used :
O(V*V)
Adjacency List
Adjacency List is an array of linked list.
The size of the array is the number of vertices in the graph.
Indices of the array represent each node or vertex of the graph.
Each node or vertex has its own linked list and each node in this linked list contains the reference to the other nodes sharing an edge with the current vertex.
For weighted linked lists, the weights can be stored in the nodes of the linked lists.
Indices of the array represent each node or vertex of the graph.
If e is the number of nodes,
For an undirected graph, The total space used is
O(n + 2e)
For an directed graph, the total space used is
O(n + e)