Graph
In a programming interview, one of the most favorite questions is about Graph. It is a non-linear data structure. It is a set of vertices and edges. There are two types of Graph; unredirected (two-way relationship) and redirected (one-way relationship).
Representation
There are three ways to represent Graph; Adjacency Matrix, Adjacency List, and Adjacency Set.
Adjacency Matrix
A two-dimensional boolean matrix which rows and columns represent the vertices. Each cell represents the edges, the relationship between the vertices.
Adjacency List
Each vertex has a pointer to a linked list. The linked list contains the other nodes that the vertex connects to.
Adjacency Set
Similar to Adjacency List. Instead of using a linked list, it is using a set. A set is a two-dimensional boolean matrix. Each entry indicates the incident of the edge.