Connecting the dots (graph representation)

Intro

A short blog about what is a graph and how you represent one.

What is a graph

A graph is a way of representing a network, this network could be any kind of network, a circuit network, a friends network (like facebook, instagram etc) and so on.

A graph looks like the following picture:

So, a graph is just a set dots that might be connected with each other.

Graphs are composed by two elements:

1. vertices: the dots (the singular is vertex)
2. edges: the lines between the vertices

how you can represent a graph

The two main representations of a graph are through an adjacent list and a adjacent matrix.

adjacent list

A adjacent list is a list (in js can be an array) that each index of the list uniquely represents a vertex (a dot).
The contents of each list element is another list (this can also be an array in js) that contains adjacent vertices.

For example, the above graph in the image can be represented with the following adjacent list:

var graph = [[2], [2, 5], [0, 1, 4], [4], [3, 5], [1, 4]];

The array index is used as a vertex unique identifier and the contents are the adjacent vertices to this vertex (again the contents are representing vertex ids).

So, in the example above:

• the vertex with id 0 (array index) has one adjacent vertex with id 2

• the vertex with id 1 (array index) has two adjacent vertices with ids, 2 and 5

• the vertex with id 2 (array index) has three adjacent vertices with ids, 0, 1 and 5

• the vertex with id 3 (array index) has one adjacent vertex with id 4

• the vertex with id 4 (array index) has three adjacent vertices with ids, 3, 2 and 5

• the vertex with id 5 (array index) has two adjacent vertices with ids, 1 and 4

adjacent matrix

A adjacent matrix is a two dimensional matrix that each dimension size is equal to total vertices of the graph and the value represents if there is an edge between the two vertices (in a simple form 1 if there is an edge and 0 if not).

For example, the above graph in the image can be represented with the following adjacent matrix:

var graph = [[0, 0, 1, 0, 0, 0],
             [0, 0, 1, 0, 0, 1],
             [1, 1, 0, 0, 1, 0],
             [0, 0, 0, 0, 1, 0],
             [0, 0, 1, 1, 0, 1],
             [0, 1, 0, 0, 1, 0]];

• the vertex with id 0 (array index) has one adjacent vertex with id 2, the first array (with index 0) values at index at index 2 must be 1

• the vertex with id 1 (array index) has two adjacent vertices with 2 and 5, the second array (with index 1) values at index 2 and 5 must be 1

In the same fashion the following entries are marked either 1 or 0. The above matrix is an bidirectional graph (e.g. if there is a way from one dot to another dot, the reverse also holds).

When to use a adjacent list or matrix?

• In real life, the adjecent list is used more frequently, since the most networks are not dense (are sparse).

• If you have to represent a dense network is better to use a adjacent matrix (the downside of the adjacent matrix is that uses a lot of space O(n^2)).

Cheers!