The algorithm:

This is an algorithm used to traverse a graph consisting of nodes and edges. In this, we traverse a graph “breadth-wise”. This means we visit all the nodes of the graph by going down the different levels of the graph. However, this poses a problem. Since we are talking about a graph, there is a possibility of loops. This would result in an infinite loop as we will keep visiting the same node again and again. To get past this problem, we will have to use a boolean visited array. This marks nodes as visited so that we do not visit them again.

To visualise this algorithm, we will utilise a queue data structure, a boolean visited array and a graph. This queue data structure follows a first-in-first-out rule.

For example:

Consider the following graph:

We start by visiting node 0.

We push it into the queue, mark it as visited and also print it.

Queue =[0]

Visited array = [true , false , false , false , false , false]

Output = 0    

The graph becomes:

Next, we look at the unvisited adjacent nodes of 0. We find that these are node 1 and node 2. We add these to the queue and also mark them as visited. Then, we also pop 0 from the queue and print the first element of the queue, i.e., 1.

Queue = [1 , 2]

Visited array = [true , true , true , false , false , false]

Output = 0 , 1

The graph becomes:

Now, we search for the adjacent, unvisited nodes of 1. We find that it is node 3. We add this to the queue and also mark them as visited. We then pop 1 from the queue and print the first element of the queue, i.e., 2.

Queue = [2 , 3]

Visited array = [true , true , true , true , false , false]

Output: 0 , 1 , 2

The graph becomes:

Next, we move on to the adjacent unvisited nodes of 2. We find that none exist. We then pop 2 from the queue and print the first element of the queue, i.e., 3.

Queue = [3]

Visited array = [true , true , true , true , false , false]

Output = 0 , 1 , 2 , 3

The graph becomes:

Now, we search for adjacent unvisited nodes of 3. We find that these are 4 and 5. Hence, we add these to the queue and mark them as visited. We then pop 3 from the queue and print the first element of the queue, i.e., 4.

Queue = [4 , 5]

Visited array = [true , true , true , true , true , true]

Output = 0 , 1 , 2 , 3 , 4

The graph becomes:

Next, we move on to the adjacent unvisited nodes of 4. We find that none exist. We then pop 4 from the queue and print the first element of the queue, i.e., 5.

Queue = [5]

Visited array = [true , true , true , true , true , true]

Output = 0 , 1 , 2 , 3 , 4 , 5

The graph becomes:

Only 5 remains in the queue and it doesn’t have any adjacent unvisited nodes. Thus the entire graph has been traversed and 5 is popped from the queue.

This is how the bfs algorithm would work.

The program:

Following is the implementation of the above program in C++:

#include <iostream>
#include <list>
using namespace std;

class graph
{
    int v;

    list<int> *adj;

public:
    graph(int v);
    void edge(int u, int v);
    void bfs();

};

graph::graph(int v){
    this->v = v;
    adj = new list<int>[v];
}
void graph::edge(int u, int v) {
    adj[u].push_back(v);
}
void graph::bfs(){

    bool *visits = new bool[v];
    for (int i = 0 ; i < v ; i ++){
        visits[i] = false;
    }
    list<int> q;
    visits[0] = true;
    q.push_back(0);
    int s = 0;
    list<int>::iterator i;
    while (!q.empty()){
        s = q.front();
        cout << s << " " ;
        q.pop_front();
        for(i = adj[s].begin();i!=adj[s].end();i++){
            if (visits[*i]==false){
                q.push_back(*i);
                visits[*i] = true;
            }
        }
    }
}
int main(){
    graph g(6);
    g.edge(0,1);
    g.edge(0,2);
    g.edge(1,0);
    g.edge(1,3);
    g.edge(2,0);
    g.edge(3,1);
    g.edge(3,4);
    g.edge(3,5);
    g.edge(4,3);
    g.edge(5,3);

    cout << "BFS implementation: " << endl;

    g.bfs();

    return 0;

}

The output of the above program is:

Time complexity of breadth first traversal:

  • Using adjacency matrix: O(V2)
  • Using adjacency list: O(V+E)

Where V is the number of vertices and E is the number of edges.

The github link for the above program is:

https://github.com/HSNA243/C-Programs/blob/master/BFS_Search.cpp

Visits: 127

2 Replies to “Breadth First Traversal”

Leave a Reply

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