6. Connecting the dots — Big O and Graph Data Structure

In this article, let us see how Graph data structure works. Graphs are non-linear data structure like trees. Graphs consists of vertex (or node) and edge (or arrows or connection). When they are connected they form a network which can be in one direction or both direction.

Graph with vertices and edges

Graphs are used in routing protocols in networks, GPS application and friends connected in social media.

Types of Graphs

• Undirected / bi-directional
• Directed / Unidirectional

When connected bi-directionally, graphs are represented with a single line and unidirectional ones are represented with an arrow pointing to one vertex like in the example shown above.

Binary tree is also a graph which points to two items and are directional.

Storing Graphs

There are two ways to represent storage of graphs

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix

These are two dimensional matrix which contains 0 or 1. When an undirected graph vertex connects to another vertex then it will represented with 1 otherwise represented as 0 thus creating a pattern. Here the patterns are symmetrical like a mirror image across a bidirectional graph.

Following is an example of how adjacency matrix works on undirected graph.

Adjacency Matrix for bidirectional graph with edges connected in both vertices

The symmetry is no more present in directed / unidirectional graph.

Adjacency matrix forming asymmetrical directed graph

Adjacency List

This is very similar to the matrix. Adjacency lists are stored with vertex as key and edges as values like below.

Adjacency list is stored as objects

Big O of Graph

When it comes to space complexity, storing using adjacency matrix becomes very inefficient because both 0’s and 1’s needs to be stored. Therefore, the space complexity is number of vertices squared. Big O of adjacency matrix is O(Vertices ²). Whereas the space complexity of adjacency list to store the vertex and edges is Big O (vertex + edge).

Now let us take a look at the implementation of graphs for the following using Adjacency List

1. Adding a VERTEX

Adding a vertex

2. Adding an EDGE

Adding an Edge

3. Removing an EDGE

Here we are building a graph with three vertices “a”, “b”, “c” which are connected. The following code removes the edge between “a” and “b” vertices which is shown in the output as true in the browser console.

Removing an an Edge

4. Removing a VERTEX

Removing a vertex

Graphs are used for solving real life situations such as network applications (such as peer to peer connections, routing), social media applications, website crawlers etc.

To summarize, time complexity of adding an edge or a vertex for Adjacency List will be BigO(1) while removing an edge takes BigO(E) as traversing of all edges is required(depends on the size of the graph and the number of edges). Finally, removal of vertex takes Big O(V+E) time as all the edges needs to be removed along with the vertex.

Hope you enjoyed this article.Thanks for reading and please follow me and give a 👏 .

Resources:

Data structures and algorithms with JavaScript, Learning JavaScript Data Structures and Algorithms, Grokking Algorithms, , algorithm , wikipedia.