Graph Traversals and it’s Application

In the previous post we gave to the Overview of Graph Data Structures.

In this post, we will discuss about Graph Traversals and also some problems based upon it. So, let’s start.

Basic Graph Traversals

There are basically two types of Graph Traversal –

(i) DFS (Depth First Search)
(ii) BFS (Breadth First Search)

We are familiar with these Traversals as we have discussed it in Tree Data Structure and the concept is similar to it.

DFS Traversal

The concept behind DFS traversal is something like we start from a source vertex , print that vertex and then move to its adjacent vertex.

Again we print it’s adjacent vertex and again move to it’s adjacent’s adjacent vertex.

We continue this process until we reach a point where no adjacent vertex remains to be explore. At this moment we backtrack and search for other unvisited vertex.

Also we maintain a visited array so that we cannot revisit the visited vertex again.

Let’s understand it by an example,

Graph Data Structure

The pictorial Diagram below is the Adjacency List of the above Graph.

Now we will explore vertex by DFS Traversal. We will start from 1 (source vertex).

Visit vertex 1 and move to it’s intermediate adjacent. The intermediate adjacent of vertex 1 is 2.

Visit vertex 2, and move to it’s intermediate adjacent. The intermediate adjacent of 2 is 1 from adjacency List.

Since vertex 1 is visited, we will not visit it again and we will find unvisited adjacent vertex of vertex 2.

The next unvisited adjacent of 2 is 3.

We will continue the process and visit remaining vertices.

Therefore DFS Traversal will be : 1 2 3 4 5 for the above graph.

Let’s take another example,

Adjacency List of above Directed Graph is,

Let’s see the DFS Traversal Traversal of the above Graph. Let source vertex be 0,

Since 1 has no adjacent vertex to explore we will go back to 0 again,

Now, vertex 5 has no adjacent vertex to explore, so again it will go back to vertex 3.

Vertex 3 also don’t have any vertex to explore, so again it will go back to 2.

DFS Traversal : 0 1 2 3 5 4 6

Hope you understood the concept behind DFS Traversal. Now let’s see the Algorithm.

DFS Algorithm

From the above discussion, it is clear we will use recursion for DFS Traversal.

The Logic is simple, we will start from source and we will recursively go to its adjacent vertex and visited it.

Continue this step until we reach a node where there s no more vertex to explore.

We will come back to the previous recursion and explore other unvisited nodes, again we will backtrack until we visit all the vertices.

Let’s see the code,

unordered_map<int, vector<int>> m;
void DFS(int s, int *vis)
{
     vis[s] = true;
     for(auto i = m[s].begin(); i != m[s].end(); i++)
     {
           if(vis[*i] == false)
           {
                 DFS(*i, vis);
           }
     }
}   

unordered_map( ) is our adjacency List and vis[] is the array that keeps track of nodes whether they are visited or not. Initially elements vis[] array is false.

Code is simple, we start from source and update the vis[] array. After that we run a loop and find the unvisited neighbours. If found we call them recursively or else we backtrack.

Time Complexity : O(V+E)
Space Complexity : O(V)


Hope DFS Traversal is clear, let’s move to our next Graph Traversal that is BFS.

BFS Traversal

In BFS traversal, we start from a source vertex, explore that vertex (Visit and print all the neighbours of that vertex) before moving to the next vertex.

Let’s take an example to understand it,

Tree Data Structure

Adjacency List of the above Graph is shown below. Let’s consider source vertex as 0.

First, visit vertex 0 and explore (visit and print) all of its neighbours,

BFS Traversal : 0 1 2

Since, we have explore all the neighbours of 0. Now we will move to its intermediate neighbour (vertex 1).

Vertex 1 doesn’t have any neighbours to explore, so we will move to next intermediate neighbour of 0 (vertex 2).

Explore neighbours of vertex 2,

BFS Traversal : 0 1 2 3 4

Since we have explored neighbours of 2, we will move to it’s next neighbour (vertex 3) and explore its neighbours.

BFS Traversal : 0 1 2 3 4 5

No, more neighbours of Vertex 3 is there, so we will move to vertex 4 and explore it neighbours.

NOTE we should have moved to vertex 5, but vertex 4 was visited earlier so we will explore vertex 4 first then vertex 5 (First Cum First Serve basis).

BFS Traversal : 0 1 2 3 4 5 6

Now, we will move to vertex 5 but it doesn’t have any neighbours to explore so lastly we will move to vertex 6 and it also doesn’t have any vertex to explore, so this way we end the BFS Traversal.

BFS Traversal : 0 1 2 3 4 5 6

Hope BFS Traversal concept is clear to you. Let us see it’s Algorithm.

BFS Algorithm

From the above illustration you might have guessed the type of data structure requires for BFS Traversal.

Yes, you guessed it right, we will require a queue to implement BFS.

Let’s discuss how Queue will help us,

First insert the source node in the queue and then run a loop until queue is empty. In between, pop the current node and push it’s neighbours to the queue. That’s it.

For above let’s see the use of queue,

Source vertex is 0, now let’s see the operations on Queue,

Hope now BFS Traversal is clear to you. Let’s see the code,

unordered_map<int, vector<int>> m;
void bfs(int s, bool *vis)
{
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        
        if(vis[t] == false)
        {
             cout<<t<<" ";
             for(auto i = m[t].begin();i != m[t].end();i++)
             {
              	 q.push(*i);
             }
             vis[t] = true;
         }
    }
}

Code is simple and I don’t think it need any further explanation. Hope you understood the concept behind both the Traversals.

Time Complexity : O(V+E)
Space Complexity : O(V)


Traversal of Adjacency List take O(V+E) complexity and since BFS Traversal requires a queue, therefore space Complexity is O(V).

Let’s move ahead,

Applications of DFS and BFS

Some of the Applications of DFS and BFS are listed below,

Application of DFS,
(i) Cycle Detection
(ii) Number of Connected Components
(iii) Path Finding
(iv) Topological Sorting (DAG)
(v) Strongly Connected Components

Application of BFS,
(i) Shortest Path in unweighted Graph
(ii) Cycle Detection
(iii) Topological Sorting (Kahn’s Algorithm)
(iv) GPS Navigation
(v) Social Network Websites
(vi) Crawlers in Search Engines

We will discuss each and every Applications. Some in this post and some in Upcoming posts. So Stayed tuned.

Number of Connected Components

The Graphs we have discussed earlier and connected Graphs and it has only one connected Component but a Graph can also be disconnected and it can also have more than one components.

Our task is to find the number of connected components in an undirected Graph.

Let’s see an example,

Number of connected Component of above Graph is 2.

Hope you understood the problem. Now write an algorithm to implement it.

Algorithm to implement Connected Components

The logic is very much simple, to implement the above problem, we simply need to do either BFS or DFS traversal starting from every unvisited vertex, and we will get all connected components.

In this post, we will implement it by DFS and you will implement it by BFS in home, if doubt arises post it in comment section.

Let’s see the code,

unordered_map <int,vector<int,int> m;
void dfs(int s, bool vis[])
{
    vis[s] = true;
    for(auto i = m[s].begin(); i != m[s].end(); i++)
    {
        if(vis[*i] == false)
        {
            dfs(*i,args,vis);
        }
    }
}
 
int main()
{
    int n,e;
    cin>>n>>e;

    for(i = 0; i < e; i++)
    {
        int x, y;
        cin>>x>>y;
        
        args[x].push_back(y);
        args[y].push_back(x);
 
    }
    bool vis[n+1] = {false};
    
    for(i = 1;i <= n;i++)
    {
        if(vis[i] == false)
        {
            dfs(i,args,vis);
            c++;
        }
    }
    cout<< c <<endl;
}

Code is simple, we simply did DFS Traversal for every unvisited vertex. In one DFS Traversal, it will visit all nodes of one component.

If there is only one connected component of the Graph then DFS Traversal will be done once.

Therefore number of DFS() call from main is our desired answer. Hope code and logic is clear to you.

Shortest Path between two nodes in undirected Graph

We are given a undirected Graph and we have to find the shortest distance from source vertex to destination vertex.

Let’s see an example,

Shortest Distance between vertex 0 and vertex 6 is 3.

Hope Problem is clear, now think of an algorithm to implement the above problem.

Algorithm to find shortest Distance

Since Graph is undirected, we will use BFS Traversal to find the shortest distance.

If you observe carefully, during BFS Traversal we are actually visiting any node from the source vertex in the shortest way.

Since we are exploring every neighbour vertex of the current vertex, it’s obvious that we are visiting that particular vertex in the shortest way.

Let’s understand it by the above example,

Neighbours of 0 is 1 and 2, so we can visit both the vertex at the cost of 1 unit. Isn’t it ?

Now, since our destination vertex is 6, from vertex 2 we can visit vertex 3 and vertex 4 at the cost of 1 more unit.

And from vertex 4, we will reach vertex 6, so through BFS we are visit any vertex in Graph in the shortest way.

Hope you understood the logic. Let’s see the code,

unordered_map <int,vector<int,int> m;
void bfs(int s, int d, bool vis[])
{
     queue<pair<int,int> q;

     q.push(make_pair(s,0));
     vis[s] = true;

     int res, f = 0;

     while(!q.empty()) 
     {
	 pair <int,int> x = q.front();
	 int p = x.first;
	 int dist = x.second;
	 q.pop();
		
	for(auto i = args[p].begin(); i != args[p].end();i++)
        {
	    if(*i == d)
            {
                res = dist;
                f = 1;
                break;
            }
            if(vis[*i] == false)
            {
	         vis[*i] = true;
		 q.push(make_pair(*i,dis+1));
	    }
	}
        if(f == 1) break;
    }
    cout << res;
}

The above code will give us the shortest distance. We simply did BFS Traversal and simultaneously updated the reachable distance from that node.

Hope code and logic is clear to you.

Shortest Distance from vertex 0 to vertex 6

In this post we did the Graph Traversal as well as some applications of it. In next post we will continue with the application part.

That’s all Folks..!!!

Tagged : / / / / /

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

Tagged :