bfs and dfs program in c++ with output

In this tutorial, i will show you bfs and dfs program in c++ with output.

The main difference between breadth first search and depth first search is in the manner in which the adjacent nodes to a starting nodes are visited.

In bread first search, all the immediate adjacent nodes to a starting node are visited – hence the name breadth first, while in depth first search, only a single node that is adjacent to a starting node is visited and then the next node to the last visited node is visited and then the next node to the last visited node is visited and then the next node to the last visited node is visited until we arrive at a node without a node to visit or whose adjacent nodes have already been visited, at which point we begin to backtrack until we arrive at our starting node and from there begin the same process in a different path. Once, we have visited all the nodes in that path, we backtrack until we reach our starting node again. This continues until we have finished visiting all our nodes or vertexes.

Let consider the difference in bfs and dfs using this example graph.

Breadth First Search Procedure Explained

Let’s pick a node to start from in the graph above: so i start with node 2. We start from node 2 – so node 2 is visited and also the value 2 is inserted into a queue, there are three adjacent or breadth first nodes connected to node 2, which are nodes 1, 3 and 5 – so we must visit all three nodes first as per bfs rule. We can visit them in any order we want: 1, 3, 5; 3, 5, 1 or 5, 3, 1; that is up to you to decide and that will reflect in the order you store the nodes in your adjacency list. In my c++ code example below, i visited the nodes in the order: 1, 3, 5; hence the way i also store them in my adjacency list.

v[2].push_back(1);
v[2].push_back(3);
v[2].push_back(5);

As we visit nodes 1, 3, 5, we insert the values 1, 3, and 5 in queue (in that order) so that when we are done visiting these nodes, we can know the next node or vertex whose adjacent nodes are to be visited by picking the first value found in the queue; once that value is picked, it should be deleted from the queue. So once we are done, we pick the next available value from the queue and visit all its adjacent nodes (i.e if not already visited). So from what we can see from the graph, the adjacent nodes of node 1 are nodes 2 and 4, but node 2 is already visited (and marked as such in an array which we initialize for the purpose of marking already visited nodes), hence; only node 4 is visited (and its value inserted into the queue) on this occasion and our visited nodes look thus at the moment: 2, 1, 3, 5, 4. Next we pick the next available value in the queue – which is now 3 and visit all its adjacent nodes. So node 3 has nodes 2 and 6 as its adjacent nodes; but node 2 has already been visited, so node 6 is visited and 6 is inserted into the queue, hence our visited nodes look thus at the moment: 2, 1, 3, 5, 4, 6. Then we pick 5 and discover all of its adjacent nodes are already visited and also marked accordingly in the visited array; then we pick 4 and discover same thing, then we pick 6 and discover same thing; and with that we are done.

Depth First Search Procedure Explained

DFS utilizes stack and so a recursive function is best for implementing this procedure. Let’s start with node 2 again – Node 2 is visited and the value 2 is pushed into the call stack and the array variable called visited is marked 1 for the index 2. Next retrieve the first adjacent node to node 2 and repeat the procedure all over again. According to the way i structured the adjacency list, the first node to be retrieved for all adjacent nodes to node 2 is node 1, so node 1 is visited next and its value is pushed to the call stack and what we have now as visited nodes is: 2, 1 and what we have in the call stack is 1, 2 (1 is the top most value in the stack because it entered the stack last). Node 1 adjacent nodes are node 2 and 4 stored in that order in the adjacency list. Node 1 then calls node 2 (and the stack is updated to: 2, 1, 2) but finds that node 2 has been visited already and so control returns to the calling function (2 is removed from the call stack and the stacks gets updated to: 1, 2) and node 4 being the second adjacent node to node 1 is rather visited and its value pushed to the stack – and so what we have now as visited nodes is: 2, 1, 4, while the call stack is 4, 1, 2. Node 4 then calls 1 (and 1 is added to call stack: 1, 4, 1, 2) but finds that 1 is already visited, call returns to 4, 1 is removed from call stack (call stack back to 4, 1, 2). Node 4 has no more adjacent nodes to call, so control return to calling function where the function was called with the value 1 (call stack gets updated to: 1, 2). Node 1 adjacent nodes are 2 and 4 which are already visited, so still control goes one step back to when the recursive function was called with the value 2 (only the value 2 is in stack now). 2 calls 3 (2 is going in a different path now) and what we have as visited nodes now is: 2, 1, 4, 3 and 3 is pushed into the call stack (call stack gets updated to: 3,2). You should have some practice – so continue with the procedure on pen and paper and you should arrive at : 2, 1, 4, 3, 6, 5 as the nodes visited at the end of the day.

BFS and DFS program in c++

#include <bits/stdc++.h>;

using namespace std;

int const N = 10;
int visited[N];
vector<int> v[N];

void BFS(int i){

    queue<int> q;//c++ stl queue initialized here
    cout<<i<<" ";//print the very first vertex visited
    visited[i] = 1;//mark the very first vertex as visited
    q.push(i);//insert the very first vertex in queue

    while(!q.empty()){//as far as there is a vertex value in queue, go on
        i = q.front();//retrieve vertex value from queue
        q.pop();//delete that vertex value from queue
        for(auto n : v[i]){//if vertex 1 is poped from queue, then we are dealing with all vertexes connected to vertex 1 in this pass
            if(visited[n] != 1){//if the vertex has not yet been visited, go on
                cout<<n<<" ";//print vertex
                visited[n] = 1;//mark vertex as visited
                q.push(n);//insert vertex value to queue
            }
        }
    }
}

//DFS implemented with this simple recursive function
//dfs requires stack and recursive calls uses stack,
//hence the decision to use a recursive function
void DFS(int i){
    if(visited[i])//first check if this node has been visited before
        return;//if visited, return to the calling function i.e backtrack
    cout<<i<<" ";//print node's value
    visited[i] = 1;//mark node as visited
    for(auto x : v[i])//retrieve adjacent nodes to the last visited node
        DFS(x);//pick the first of the adjacent node to be retrieve and repeat the process
}

int main()
{
    //store vertex and edges in adjacency list
    //vertex 1 is connected to vertex 2, hence
    //the code v[1].push_back(2);
    //vertex 1 is also connected to vertex 4, hence
    //the code v[1].push_back(4);
    //now you should get the idea of what i am
    //doing here
    v[1].push_back(2);
    v[1].push_back(4);
    v[2].push_back(1);
    v[2].push_back(3);
    v[2].push_back(5);
    v[3].push_back(2);
    v[3].push_back(6);
    v[5].push_back(2);
    v[5].push_back(6);
    v[6].push_back(3);
    v[6].push_back(5);
    v[4].push_back(1);

    BFS(3);//you can start with any vertex, i am starting with 3

    cout<<"\n\n";

    //reset visited[N]
    for(int i=0;i<N;i++)
         visited[i] = 0;//reset all elements to 0

    DFS(2);//you can start with any vertex, i am starting with 2
}

Program Output

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

You May Also Like