A graph is a non-linear data structure consisting of vertices (v) or nodes and edges (e) or arcs.
The graph is denoted by G(E, V).
Undirected graphs
Undirected graphs have edges that do not have a direction. The edges indicate a two-way relationship, in that each edge can be traversed in both directions.
Directed graphs
A graph in which each graph edge is replaced by a directed graph edge is called a directed graph or digraph.
Solutions
Method 1: Adjacency List
An adjacency list represents a graph as an List of Lists.
The index of the list represents a vertex and each element in its list represents the other vertices that form an edge with the vertex.
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(n^2).
Method 2: Adjacency Matrix
An adjacency matrix is a 2D array of n x n vertices. Each row and column represent a vertex.
If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j.
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(n^2).