BFS (Breadth-First Search) in Binary Trees and Graphs

BFS (Breadth-First Search) is one of the simplest algorithms for traversing a graph. Prim’s min-spanning-tree and Djikstra’s algorithm use similar ideas as BFS. BFS is also known as Level-order traversal because the algorithm discover all nodes at distance k from root before discovering any nodes at distance k+1.

Pseudocode for BFS

Let G be the graph/tree and s be the source node/root. We’ll maintain a vis (visited) array to mark a node as visited ie for node i, vis[i] is 1 if it has been visited already, otherwise vis[i] will be 0. We’ll use Queue – data structure for performing BFS traversal. Let Q be the required queue.

BFS (G, s)
vis[s] = 1
Enqueue (Q, s)

while (!Q.empty()):
  u = Q.front()
  Q.pop()

  for each v ∈ Adjacent(u):
    if vis[v] === 0:
      vis[v] = 1
      Enqueue(Q, v)
  end

end

Time complexity for Breadth-First Search is O(n) where n is the number of nodes. This is because each node is visited only once.

Note: We advise you to try implementing BFS for a graph yourself before reading the implementation in C++ below:

Implementation for a Binary Tree
Binary Tree

Level Order traversal for above tree is: 1, 20 21, 30 31

Code Implementation

//
//  main.cpp
//  BFS Binary Tree
//
//  Created by Himanshu on 26/08/21.
//

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

struct node {
    int value = 0;
    struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data) {
    node* Node = new node();
    Node->value = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}

void BFS (Node *root) {
    if (root == NULL) {
        return;
    }

    queue<Node*> qu;
    qu.push(root);
    int level = 0;

    cout<<"Level order traversal:";
    while (!qu.empty()) {

        int size = (int) qu.size();
        cout<<endl<<"Level: "<<level<<endl;

        for (int i=0; i<size; i++) {
             Node* curr = qu.front();
             cout<<(curr->value)<<" ";

             qu.pop();

             if (curr->left) {
                 qu.push(curr->left);
             }

             if (curr->right) {
                 qu.push(curr->right);
             }
        }

        level++;
    }

    cout<<endl;
}

int main() {
    Node *root = newNode(1);
    root->left = newNode(20);
    root->right = newNode(21);
    root->right->left = newNode(30);
    root->right->right = newNode(31);

    BFS (root);

    return 0;
}

Output

Level order traversal:
Level: 0
1 
Level: 1
20 21 
Level: 2
30 31 

Here’s a working example: BFS (Binary Tree)

Implementation for a Graph
Unweighted Graph


BFS traversal for above graph is: 1, 2 3, 4, 5

Code Implementation

//
//  main.cpp
//  BFS Graph
//
//  Created by Himanshu on 26/08/21.
//
#include <iostream>
#include <queue>
using namespace std;

//s= source
//n = number of nodes in graph
void BFS (int s, int n, vector<int> graph[]) {
    if (s == 0) {
        return;
    }

    int vis[n+1];
    queue<int> qu;
    
    for (int i=1; i<=n; i++) {
        vis[i] = 0;
    }

    qu.push(s);
    vis[s] = 1;

    cout<<"BFS:"<<endl;
    cout<<s<<endl;

    while (!qu.empty()) {

        int node = qu.front();
        qu.pop();

        for (int i=0; i<graph[node].size(); i++) {
            int j = graph[node][i];

            if (vis[j] == 0) {
                vis[j] = 1;
                qu.push(j);
                cout<<j<<" ";
            }

        }

        cout<<endl;
    }

    cout<<endl;
}


int main() {
    int s = 1, n = 5;
    vector<int> graph[n+1];

    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(1);
    graph[2].push_back(4);
    graph[3].push_back(1);
    graph[3].push_back(5);
    graph[4].push_back(2);
    graph[4].push_back(5);
    graph[5].push_back(3);
    graph[5].push_back(4);
    
    cout<<"Graph:"<<endl;
    for (int i=1; i<=n; i++) {
        cout<<i<<": ";

        for (int j=0; j<graph[i].size(); j++) {
            cout<<graph[i][j]<<" ";
        }

        cout<<endl;
    }

    cout<<endl;

    BFS(s, n, graph);

    return 0;
}

Output

Graph:
1: 2 3 
2: 1 4 
3: 1 5 
4: 2 5 
5: 3 4 

BFS:
1
2 3 
4 
5 

Here’s a working example: BFS (Graph)

In the next post we’ll learn about DFS (Depth-First Search)

Leave a Reply

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