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

Directed Graph
Directed Graph. Source: https://en.wikipedia.org/wiki/File:Directed.svg
Undirected Graph
Undirected Graph. Source: https://en.wikipedia.org/wiki/File:6n-graf.svg

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.

Related Articles