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

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

- Adjacency Matrix
- 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.

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

**Adjacency List**

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

# 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

*Adding a**VERTEX*

2. *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.

4. *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**.*