graph data structure

Graph Data Structure | Complete Overview

In this post, we are going to discuss a widely used data structure Graph.

The graph data structure is used almost everywhere in our daily life. Google Maps, Social networking sites, GPS Navigation are some of the applications of Graph.

It a very easy and conceptual topic to understand. You will definitely love the process of learning. So let’s start.

What is a Graph Data Structure ?

The graph data structure is a collection of vertices and edges. Vertex represents the node and edges defines the connectivity between them.

graph data structure

Every pair of vertices are connected by edges.

The minimum number of vertices required to form a Graph is 1 but a minimum number of edges to form a Graph is 0.

So, Graph can even contain n vertices without any edge and this type of Graph is called a NULL Graph.

Graph can also have parallel edges and self-loops as well.

Types of Graph Data structure

Graphs are classified into two categories –

(i) Undirected Graph: In undirected Graph, for every pair of vertices, the edge is defined as a bidirectional edge.

An edge between node x and node y is also considered as an edge between node y and node x.

(ii) Directed Graph: In a directed Graph, for every pair of vertices, the edge is defined as a unidirectional edge.

An edge between node x and node y doesn’t mean there is also an edge between node y and node x.

The below diagram represents a Directed Graph.

Learn Tree Traversal

graph data structure

There are many other types of Graphs as well like Bipartite Graph, Weighted Graph, etc. We will discuss it later when we will solve Questions based upon it.

Representation of Graphs

Now, you might be thinking how can we represent Graphs in our system to deal with real-life problems..?

We have already learned about the tree data structure. Let me tell you that Tree is also a Graph but it is the simplest form of Graph where we have limitations that a node in the binary tree cannot have more than two children.

But in the Graph we don’t have any restrictions. Here Graph can even have parallel edges and self-loops as well.

The graph is commonly represented in two ways –

Adjacency Matrix

One of the ways to represent Graph is by Adjacency Matrix.

Let say a Graph has ‘n’ vertices, then Adjacency Matrix of dimension (n * n) represents the Graph.

Let’s see an example,

How to clone a linked list

graph data structure

Adjacency Matrix of the above Graph is,

graph data structure

Value 0 in arr[i][j] represents that there is no edge between the nodes (i & j).

Value 1 in arr[i][j] represents that there is a edge between the nodes (i & j).

NOTE above matrix is the Symmetric matrix, it shows that the graph is undirected because in undirected Graph edge between node x and y also represents the edge between node y and x.

How to create Adjacency Matrix ?

The logic behind creating Adjacency Matrix is very simple, you have to create a 2-D matrix and just have to updates the value.

Let’s see it’s code,

void create_Graph(int **arr, int n)
{
	int e,u,v;
	scanf("%d",&e);                   // Number of Edges
	for(int i=0;i<e;i++)
	{
		scanf("%d%d",&u,&v);
		arr[u-1][v-1] = 1;
		arr[v-1][u-1] = 1;
	}
}
int main()
{
	int n;
	scanf("%d",&n);                  //Number of Vertices      
	
        int **arr;
        arr = malloc(n * sizeof(int*));
  	for(int i=0; i<n; i++)
  	{
    		arr[i] = malloc(n * sizeof(int**));
  	}
       
        for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			arr[i][j] = 0;
		}
	}
	create_Graph(arr,n);
	return 0;
}

I hope the code is clear to you. The Problem with Adjacency Matrix is that it allocates space for the edges which are not present.

For matrix values 0, there is no edge present between those vertices. So it’s is unnecessary to allocate extra space for it.

Time Complexity: O(n^2)
Space Complexity: O(n^2)

The Solution to the above problem is the Adjacency List.

Rat in A Maze Problem MasterStroke

Adjacency List

The problem to Adjacency Matrix it require extra time as well as extra space for representing a Graph.

Adjacency List is the solution to the above problem. In Adjacency List we create a list for every vertices.

If there is an edge between node x and node y, we will add y to the list of x and for undirected Graph we will add x to the list of y as well.

Let’s see an example,

graph data structure

For above matrix, adjacency list will be,

graph data structure

For each vertex there is a list which denotes the edge. Like in the above example, there is an edge between (B, A) as well as between (B, E).

How to create Adjacency List ?

In C++ creating adjacency list is very easy, but in C we have to declare a structure for creating the List.

We will discuss both the approach, let’s discuss how will you create adjacency list in C

struct Node 
{
      char vertex;
      struct Node* next;
};

struct Graph 
{
      int vertices;
      struct Node **adjacency_list; 
};

We will use two structures for creating adjacency list, one for declaring a node and other for declaring the adjacency list.

struct Node **adjacency_list;

The above line will store the address of the head pointer of every vertex. So we have used double-pointer.

A pointer is used to store the address of a variable but since the head pointer of every vertex is already an address, so to store head pointer we use double-pointer to store its address.

Double Pointer is used to store the address of the address of a variable.

Let’s see code for creating Adjacency list is C,

struct Node
{
	char vertex;
	struct Node* next;
};
struct Graph
{
	int vertices;
	struct Node **adjacency_list;
};

struct Graph* create_graph(struct Graph *G, char s, char d)
{
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	
        temp->vertex = s;
	temp->next = NULL;
	temp->next = G->adjacency_list[d];
	G->adjacency_list[d] = temp;
        
        struct Node *ptr = (struct Node*)malloc(sizeof(struct Node));
        ptr->vertex = s;
        G->adjacency_list[s] = ptr;
	
        return G;
}

void main()
{
	int n;
	scanf("%d",&n);           // Number of Vertices
	
        struct Graph* G = (struct Graph*)malloc(sizeof(struct Graph));
	
        G->vertices = n;
	G->adjacency_list = malloc(sizeof(struct Node)*(n));
	
	for(i = 1; i <= n; i++) {
		G->adjacency_list[i]=NULL;
	}
	
        int e;
	scanf("%d",&e);            // Number of Edges
	
        char x, y; 
        for(int i = 0; i < e; i++)
	{
		scanf("%c %c",&x,&y);
		G = create_graph(G,x,y);
	}
        return;
}

Initially Graph will have n vertices and n number of head pointers.

int n;
scanf("%d",&n);

struct Graph* G = (struct Graph) malloc (sizeof (struct Graph )); 
G->vertices = n; 
G->adjacency_list = malloc (sizeof (struct Node) * n );

for(i = 1; i <= n; i++) 
{ 
     G->adjacency_list[i]=NULL;
}

The above will just create the basic Adjacency List or it will initialize the Graph.

The below pictorial diagram represents the basic structure.

graph data structure

The create_graph( ) function will create the graph. Let’s understand it clearly.

struct Graph* create_graph (struct Graph *G, char s, char d) 
{ 
      struct Node *temp = (struct Node*) malloc ( sizeof (struct Node));
       
      temp->vertex = s;
      temp->next = G->adjacency_list[d];
      G->adjacency_list[d] = temp;

     struct Node *ptr = (struct Node*) malloc ( sizeof (struct Node));
     ptr->vertex = s;

      G->adjacency_list[s] = ptr;
      return G;
}

This code will create a node and insert it to front the required head.

Let’s us take an edge (B, E), we want to insert this edge.

graph data structure

I hope the code and logic behind it is clear to you. The above code is for Directed Graph, for undirected Graph you just have to modify create_graph( ). That’s it.

Adjacency List in C++

In C++, creating an adjacency list is a cup of tea. Thanks to unordered_map for making things easy.

The key of the map will be a char/int type for storing head of the adjacency list and value will be a vector for storing all other nodes.

unordered_map<char, vector<char>> m;

The above line will create the adjacency list and now we just have to insert data to it accordingly.

Let’s see the code,

unordered_map<char, vector<char>> m;
void create_adjacencyList(int n, int e)
{
     char s, d; 
     for(int i = 0; i < e; i++)
     {
          cin >> s >> d;
          m[s].push_back(d);
      }
}

And that’s it, we wrote the code for creating a directed graph with n vertices and e edges.

We can even create an adjacency list by taking an array of vectors. Let’s see it’s code too,

void create_adjacencyList(int n, int e)
{
     char s, d; 

     vector<char> adj[n];
     for(int i = 0; i < e; i++)
     {
          cin >> s >> d;
          adj[s].push_back(d);
      }
}

Thanks to the vector which creates the list dynamically but in C language we don’t have vectors so we have to create a link list to do all the stuff.

I hope both codes are clear. If you have doubts, comment it below. I will try to clear it out.

In this post, I discussed basics of Graph, I will continue with more Graph articles. So stay tuned.

That’s all folks..!!!

Subtree problem in Data structure

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

Leave a Comment

Your email address will not be published. Required fields are marked *