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
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
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)
One thought on “BFS (Breadth-First Search) in Binary Trees and Graphs”