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.

Table of Contents

**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,

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,

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