Representing a graph

There are a few ways we can represent graphs when it comes to data structures. There is no correct way of representing a graph among the existing possibilities. It depends on the type of problem you need to resolve and the type of graph as well.

The adjacency matrix

The most common implementation is the adjacency matrix. Each node is associated with an integer, which is the array index. We represent the connectivity between vertices using a two-dimensional array, as array[i][j] === 1 if there is an edge from the node with index i to the node with index j; or as array[i][j] === 0 otherwise, as demonstrated by the following diagram:

Graphs that are not strongly connected (sparse graphs) will be represented by a matrix with many zero entries in the adjacency matrix. This means we will waste space in the computer memory to represent edges that do not exist; for example, if we need to find the adjacent vertices of a given vertex, we will have to iterate through the whole row...