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,

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,

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

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

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.

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