Graph Data Structure
A graph is a non-linear data structure consisting of nodes and edges. Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.
In the examples below, circles represent vertices and lines represent edges
Types of graphs
A graph can be directed or undirected. In a directed graph (see below), nodes are connected by directed edges. Edges go only in one direction.
In an undirected graph (see below), nodes are connected by edges that are all bidirectional.
Graph Representations
The standard graph representation for graphs is called the adjacency-lists data structure. An adjacency-lists is an array of lists. In adjacency-lists we keep track of all the vertices adjacent to each vertex on a linked list that is associated with that vertex.
The adjacency-lists for below graph will be:
0: 1
1: 0, 2, 4
2: 1, 3, 4
3: 2
4: 1, 2
5: empty list
Another representation is called the adjacency matrix. An adjacency matrix is a 2D array of size V x V where V is the number of nodes in a graph. A element at matrix[i][j] = 1 indicates that there is an edge from node i to node j.
Here is the adjacency matrix for the same graph:
