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.
There are two ways to represent storage of graphs
- Adjacency Matrix
- Adjacency List
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.
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 👏 .