Breadth First Search (BFS) is an algorithm for traversing or searching layerwise in tree or graph data structures. BFS was first invented in 1945 by Konrad Zuse which was not published until 1972. It was reinvented in 1959 by Edward F. Moore for finding the shortest path out of a maze. BFS was further developed by C.Y.Lee into a wire routing algorithm (published in 1961). The strategy used here is opposite to depth first search (DFS) which explores the nodes as far as possible (depth-wise) before being forced to backtrack and explore other nodes. The algorithm starts at the tree root (or any arbitrary node of a graph called ‘source node’), and investigates all of the neighboring nodes (directly connected to source node) at the present level before moving on to the nodes at the next level. The process is repeated until the desired result is obtained.
Table of content
Most of the concepts in computer science and real world can be visualized and represented in terms of graph data structure. BFS is one such useful algorithm for solving these problems easily. The architecture of BFS is simple, accurate and robust. It is very seamless as it is guaranteed that the algorithm won’t get caught in an infinite loop.
Note:
Consider the following graph structure where S is the Source node to begin BFS with:
The goal here is to find whether the node E is present in the graph. Just by seeing the graph, we can say that node E is not present. Lets see how BFS works to identify this.
Step 1: We enqueue S to the QUEUE.
Step 2: Mark S as Visited.
Step 3: Now, call the BFS function with S in the queue.
Step 4: Dequeue A and check whether A matches the key. It doesnt match, hence proceed by enqueueing all unvisited neighbours of A (Here, D is the unvisited neighbor to A) to the queue.
Step 5: Dequeue B and check whether B matches the key E. It doesnt match. So, proceed by enqueueing all unvisited neighbors of B to queue. Here all neighboring nodes to B has been marked visited. Hence, no nodes are enqueued.
Step 6: Dequeue C and check whether C matches the key E. It doesnt match. Enqueue all unvisited neighbors of C to queue. Here again all neighboring nodes to C has been marked visited. Hence, no nodes are enqueued.
Step 7: Dequeue D and check whether D matches the key E. It doesnt match. So, enqueue all unvisited neighbors of D to queue. Again all neighboring nodes to D has been marked visited. Hence, no nodes are enqueued.
Step 8: As we can see that the queue is empty and there are no unvisited nodes left, we can safely say that the search key is not present in the graph. Hence we return false or “Not Found” accordingly.
This is how a breadth-first search works, by traversing the nodes levelwise. We stop BFS and return Found when we find the required node (key). We return Not Found when we have not found the key despite of exploring all the nodes.
/**
* Pseudo code for recursive BFS
* @Parameters: Graph G represented as adjacency list,
* Queue q, boolean[] visited, key
* Initially q has s node in it.
*/
recursiveBFS(Graph graph, Queue q, boolean[] visited, int key){
if (q.isEmpty())
return "Not Found";
// pop front node from queue and print it
int v = q.poll();
if(v==key) return "Found";
// do for every neighbors of node v
for ( Node u in graph.get(v))
{
if (!visited[u])
{
// mark it visited and push it into queue
visited[u] = true;
q.add(u);
}
}
// recurse for other nodes
recursiveBFS(graph, q, visited, key);
}
Queue q = new Queue();
q.add(s);
recursiveBFS(graph, q, visited, key);
/**
* Pseudo code for iterative BFS
* @Parameters: Graph G, source node s, boolean[] visited, key
*/
iterativeBFS(Graph graph, int s, boolean[] visited, int key){
// create a queue neeeded for BFS
Queue q = Queue();
// mark source node as discovered
visited[s] = true;
// push source node into the queue
q.add(s);
// while queue isnt empty
while (!q.isEmpty())
{
// pop front node from queue and print it
v = q.poll();
if(v==key) return "Found";
// for every neighboring node of v
for (int u : graph.get(v)) {
if (!visited[u]) {
// mark it visited and enqueue to queue
visited[u] = true;
q.add(u);
}
}
}
//If key hasnt been found
return "Not Found";
}
Following are C, C++, Java and Python implementations of Breadth First Search.
BFS Implementation In C:
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int n;
int adj[MAX][MAX]; //adjacency matrix, where adj[i][j] = 1, denotes there is an edge from i to j
int visited[MAX]; //visited[i] can be 0 / 1, 0 : it has not yet printed, 1 : it has been printed
void create_graph();
void BF_Traversal();
void BFS();
int queue[MAX], front = -1,rear = -1;
void push_queue(int vertex);
int pop_queue();
int isEmpty_queue();
int main()
{
create_graph();
BFS();
return 0;
}
void BFS()
{
int v;
for(v=0; v<n; v++)
visited[v] = 0;
printf("Enter Start Vertex for BFS: \n");
scanf("%d", &v);
int i;
push_queue(v);
while(!isEmpty_queue())
{
v = pop_queue( );
if(visited[v]) //if it has already been visited by some other neighbouring vertex, it should not be printed again.
continue;
printf("%d ",v);
visited[v] = 1;
for(i=0; i<n; i++)
{
if(adj[v][i] == 1 && visited[i] == 0)
{
push_queue(i);
}
}
}
printf("\n");
}
void push_queue(int vertex)
{
if(rear == MAX-1)
printf("Queue Overflow\n");
else
{
if(front == -1)
front = 0;
rear = rear+1;
queue[rear] = vertex ;
}
}
int isEmpty_queue()
{
if(front == -1 || front > rear)
return 1;
else
return 0;
}
int pop_queue()
{
int delete_item;
if(front == -1 || front > rear)
{
printf("Queue Underflow\n");
exit(1);
}
delete_item = queue[front];
front = front+1;
return delete_item;
}
void create_graph()
{
int count,max_edge,origin,destin;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edge = n*(n-1); //assuming each vertex has an edge with remaining (n-1) vertices
for(count=1; count<=max_edge; count++)
{
printf("Enter edge %d( -1 -1 to quit ) : ",count);
scanf("%d %d",&origin,&destin);
if((origin == -1) && (destin == -1))
break;
if(origin>=n || destin>=n || origin<0 || destin<0)
{
printf("Invalid edge!\n");
count--;
}
else
{
adj[origin][destin] = 1;
adj[destin][origin] = 1; // assuming it is a bi-directional graph, we are pushing the reverse edges too.
}
}
}
BFS Implementation in C++
#include<bits/stdc++.h>
using namespace std;
#define MAX 1005
vector <int> adj[MAX]; // adjacency matrix, where adj[i] is a list, which denotes there are edges from i to each vertex in the list adj[i]
bool visited[MAX]; // boolean array, hacing value true / false, which denotes if a vertex 'i' has been visited or not.
void init(){ // initialization function
int i;
for(i = 0; i < MAX; i++){
visited[i] = false; // marking all vertex as unvisited
adj[i].clear(); // clearing all edges
}
}
void BFS(int start){
init();
queue <int> q;
q.push(start);
int iterator, current_node, next_node;
cout<<"BFS Traversal is:\n";
while(q.empty() == false){
current_node = q.front();
q.pop();
if(visited[current_node] == true){
continue;
}
cout<<current_node<<" ";
visited[current_node] = true;
for(iterator = 0; iterator < adj[current_node].size(); iterator++){
next_node = adj[current_node][iterator];
if(visited[next_node] == false) {
q.push(next_node);
}
}
}
}
int main(){
int vertices, edges;
cout<<"Enter Number of Vertices:\n";
cin>>vertices;
cout<<"Enter number of edges:\n";
cin>>edges;
int i;
int source, destination;
cout<<"Enter Edges as (source) <space> (destination):\n";
for(i=0; i<edges; i++){
cin>>source>>destination;
if(source > vertices || destination > vertices){
cout<<"Invalid Edge";
i--;
continue;
}
adj[source].push_back(destination);
adj[destination].push_back(source);
}
int start;
cout<<"Enter Starting Vertex:";
cin>>start;
BFS(start);
}
BFS Implementation In Java
import java.io.*;
import java.util.*;
// This class represents a directed graph using adjacency list
// representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency Lists
// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Function which adds an edge from v -> w
void addEdge(int v,int w)
{
adj[v].add(w);
}
// Function which prints BFS traversal from a given source 's'
void BFS(int s)
{
// mark all vertices as false, (i.e. they are not visited yet)
boolean visited[] = new boolean[V];
// Create a new queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);
while (queue.size() > 0)
{
// pop a vertex from queue and print it
s = queue.poll();
System.out.print(s+" ");
//Traverse all the adjacent vertices of current vertex,
//check if they are not visited yet, mark them visited and push them into the queue.
Iterator<Integer> it = adj[s].listIterator();
while (it.hasNext() == true)
{
int n = it.next();
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
}
}
class Main {
// Driver method to Create and Traverse Graph
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter Number of vertices");
int vertices = sc.nextInt();
Graph g = new Graph(vertices);
System.out.println("Enter Number of edges");
int edges = sc.nextInt();
int i;
int source, destination;
System.out.println("Enter Source <space> Destination (0-indexing)");
for(i = 0; i < edges; i++){
source = sc.nextInt();
destination = sc.nextInt();
if(source >= vertices || destination >= vertices){
System.out.println("Invalid Edge");
i--;
}
g.addEdge(source, destination);
}
System.out.println("Enter starting vertex");
int start = sc.nextInt();
System.out.println("Following is Breadth First Traversal, starting from vertex " + start);
g.BFS(start);
}
}BFS implementation in python
import collections
class graph:
def __init__(self,adjacency=None):
if adjacency is None:
adjacency = {}
self.adjacency = adjacency
def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
seen, queue = set([startnode]), collections.deque([startnode])
while queue:
vertex = queue.popleft()
print(vertex)
for node in graph[vertex]:
if node not in seen: #checking if not visited
seen.add(node)
queue.append(node)
# The graph dictionary
adjacency = {
"a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
bfs(adjacency, "a")
Why do we prefer queues instead of other data structures while implementing BFS?
Why is time complexity more in the case of graph being represented as Adjacency Matrix?
O(V) time. Since the level covers V elements over the course of BFS, the total time would beO(V * V) which is O(V2).O(V) time, irrespective of edges.V is E. So, BFS when using Adjacency List gives O(V + E).What is 0-1 BFS?
/*
* edges[v][i]: adjacency list in the form of pairs
* i.e. edges[v][i].first contains the node to which v is connected
* and edges[v][i].second contains distance between v and edges[v][i].first.
*
* Q: Double ended queue
* distance: Array where distance[v] contain the distance from the start node to v node.
* Initially, the distance from the source node to every other node is marked infinity.
*/
void Zero_One_BFS(int start)
{
Deque <Integer > Q; //Double-ended queue
Q.push_back( start);
distance[start] = 0;
while(!Q.empty())
{
int v = Q.pop_front();
for( int i = 0 ; i < edges[v].size(); i++){
// if distance of neighbour of v from start node is greater
// than sum of distance of v from start node and edge weight
// between v and its neighbour (distance between v and its
//neighbour of v) ,then update it
if(distance[edges[v][i].first] > distance[v] + edges[v][i].second ) {
distance[edges[v][i].first] = distance[v] + edges[v][i].second;
//if edge weight between v and its neighbour is 0 then push it to front of Deque
if(edges[v][i].second == 0)
{
Q.push_front(edges[v][i].first);
}
// else push it at back
else
{
Q.push_back(edges[v][i].first);
}
}
}
}
}
Why can’t we use normal queue in 0-1 BFS technique?
What are the classifications of edges in a BFS graph?
Edge (u, v) such that v is descendant but not part of the DFS tree. Edge from node 1 to node 6 is a forward edge.Edge (u, v) such that v is ancestor of edge u but not part of DFS or BFS tree. Edge from node 4 to node 1 is a back edge.What are the types of edges present in BFS of a directed graph?
Can BFS be used for finding shortest possible path?
What is the difference between DFS and BFS? When is DFS and BFS used?
Is BFS a complete algorithm?
Is BFS a optimal algorithm?
Log In using
