InterviewBit Academy is now Scaler Academy!
InterviewBit Academy is now Scaler Academy!
Breadth-first search is a chart traversal calculation that begins navigating the diagram from the root node and investigates all the neighboring nodes. At that point, it chooses the closest node and investigates all the unexplored nodes.
The algo pursues a similar procedure for each of the closest nodes until it finds the required key, the one that is being searched for.
The data structure used in a Breadth-first algorithm is a queue and a graph. The algorithm makes sure that every node is visited at least once, and not twice. It makes sure that all the neighboring nodes for a particular node are visited, not more than once.
Consider the following example:
The above graph has 5 nodes connected to one another. The BFS traversing goes in the following manner.
The queue is empty at first, as soon as one traverses the root S, the symbol gets inserted in the queue.
Now, we look for the unexplored nodes from S. There exist three namely, A, B, and C.
We start traversing from A. Mark it as visited and enqueue.
After this, there are two neighboring nodes from A, i.e., B and C. We next visit B. And insert it into the queue and mark as visited.
The similar procedure begins with node C, and we insert it into the queue.
Now, there aren’t any neighboring nodes to C, on the same level. Thus, traversing begins at a lower level. There exists only one node at the level lower than C, which is D.
Now, we dequeue the first element.
We now traverse D, mark as visited, and insert in the queue.
As we see, there aren’t any unvisited nodes. But when there are, we keep dequeuing to insert more elements in the queue, till all the nodes are marked as visited.
Set all nodes to "not visited";
q = new Queue();
q.enqueue(initial node);
while ( q ≠ empty ) do
{
x = q.dequeue();
if ( x has not been visited )
{
visited[x] = true; // Visit node x !
for ( every edge (x, y) /* we are using all edges ! */ )
if ( y has not been visited )
q.enqueue(y); // Use the edge (x,y) !!!
}
}
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")
Log In using
