Graph Traversal using Depth First Search and Breadth First Search

Things to be discussed in this article,

Why graph traversal?
Depth-first Search (DFS)
Breadth-first Search (BFS)

Graph Traversal

Graph traversal is a process of visiting all vertices in a Graph. Why do we ever need to traverse through a graph? The simple answer is to get information out of that Graph. Now your question would be that what we will do with that information? For this, I'll say that this information will help in our Real-life applications such as building a stable internet network, to find shortest route from source city to the destination city, finding the probable faulty zone in Network, etc.

So, in particular, we have two different methods of graph traversal which are widely used application based. The first one is Depth-First Search and the second one is Breadth-First Search. Below we describe both the algorithm

Depth-first Search

The depth-first search is a straightforward graph traversal technique.
The algorithms begin at a starting node, and proceeds to all other nodes that are reachable from the starting node, and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.
The depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other paths of the graph.
The algorithm keeps track of visited nodes so that it processes each node only once.
Running time of DFS Algorithm = O( V+E )
Application of DFS

To find the number of Connected Component.
To find shortest distance from one source to all other nodes.
To find presence of a cycle in a graph.
To find the topological sorting of the graph.
To find Articulation Points, Bridges in a Graph.
etc.

The below is an explanation video for Depth-first Search.

Implementation

A depth-first search can be implemented using recursion.
The flowing DFS function begins a depth-first search at a given node.
The graph is stored as adjacency lists.
In the below implementation we try to find the distance of all nodes from a given source node for an undirected connected graph.

Here is the implementation of DFS algorithm in C++

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;

void dfs(bool visited[], int dist[], vector<int> adj[], int source){
    visited[source]=true;
    for(auto u: adj[source]){
        if(visited[u]) continue;
        visited[u]=true;
        dist[u]=dist[source]+1;
        dfs(visited,dist,adj,u);
    }
}

void solve(){
    int n,m; cin>>n>>m; // n-number of nodes, m-number of edges.
    vector<int> adj[n+1];
    for(int i=0; i<m; i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u); // undirected graph
    }

    bool visited[n+1]; // to track the given node is visited or not
    int dist[n+1]; // to store the distance from the source node.
    memset(visited,false,sizeof visited);
    dist[1]=0; // initializing source node distance from itself.
    dfs(visited, dist, adj, 1); // keeping source node as 1.

    cout<<"Nodes --> Distance\n";
    for(int i=1; i<=n; i++) cout<<i<<" --> "<<dist[i]<<"\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Breadth-first Search

Breadth-first search visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using a breadth-first search.
The breadth-first search goes through nodes one level after another. The first search goes through the nodes one level after another.
First, the search explores the nodes whose distance from the starting node is 1, then nodes whose distance is 2, and so on.
This process continues until all nodes have been visited.
Running time of DFS Algorithm = O( V+E )
Application of BFS

To find the number of Connected Component.
To find the shortest distance from one source to all other nodes.
To find the presence of a cycle in a graph.
To check whether the graph is Bipartite/ 2-Colourable or not.
etc.

The below is an explanation video for Breadth-first Search.

Implementation

A breadth-first search can be implemented using recursion.
The flowing BFS function begins a depth-first search at a given node.
The graph is stored as adjacency lists.
In the below implementation we try to find the distance of all nodes from a given source node for an undirected connected graph.

Here the implementation code of Breadth-first-search in C++.

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;

void solve(){
    int n,m; cin>>n>>m; // n-number of nodes, m-number of edges.
    vector<int> adj[n+1];
    for(int i=0; i<m; i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u); // undirected graph
    }

    bool visited[n+1]; // to track the given node is visited or not
    int dist[n+1]; // to store the distance from the source node.
    memset(visited,false,sizeof visited);
    dist[1]=0; // initializing source node distance from itself.
    visited[1]=true;

    // BFS
    queue<int> q; q.push(1);
    while(!q.empty()){
        int source=q.front(); q.pop();
        for(auto u: adj[source]){
            if(visited[u]) continue;
            visited[u]=true;
            dist[u]=dist[source]+1;
            q.push(u);
        }
    }

    cout<<"Nodes --> Distance\n";
    for(int i=1; i<=n; i++) cout<<i<<" --> "<<dist[i]<<"\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Now it's time for us to practice some problems related to DFS and BFS and enhance our 
knowledge. So to help you with this here are some problems from Codeforces.

Practice Problem

That's all for this article, in the next article we will be discussing Application of DFS - Connected Component, Articulation Point and Bridges. Before moving to the next session do practice the above problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you ).

If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.

If you think that this article has helped you to learn something then do share this with your friends.

Thank You
With 💙 by Learn DSA

Graph Traversal using Depth First Search and Breadth First Search

Post a Comment

Contact Form