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).

Directed Graph
Directed Graph. Source:
Undirected Graph
Undirected Graph. Source:


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.