Breadth First Search
Breadth First Search
Breadth first search is a graph traversing algorithm. In this, we start traversing from the source node or any selected node and traverse the graph layer by layer. Layer-wise means we need to explore the all-neighbor nodes of that selected node, which are directly connected to the source node, only after we can move to the next layer and doing the same procedure. If we do analysis of BFS, then we can say the input to breadth first search is supposed be a finite graph which can be represented by an adjacency list or adjacency matrix, or any similar representation. The breadth first search is a complete search algorithm in nature.
As the name Breadth first search proposes, we have to traverse the graph level-wise.
- We need to traverse horizontally and visit all the nodes of the current layer
- Then after, we can move to the next layer
Example:
Traversing neighbor nodes
If we talk about the graph, so a graph can contain cycles, which may create a problem while traversing the graph because that cycle may bring us to the same node again, so if we want to overcome that problem, we can use a boolean array and in this boolean array, we take the status of the node if the node is processed, then we just change the value of it. While traversing the node of the graph, we should store them in the queue to traverse the corresponding neighbor nodes in the order their parent has visited.
In the above example, we just start traversing from the source node, which is 0, and we visit its neighbor nodes 1, 2 and 3. We need to store these nodes in the order in which these nodes are traversed or visited. We can say that it allows us to visit their neighbor nodes in an appropriate manner like a neighbor of 1 node are 4 and 5, then 2 i.e., 6 and 7 and 3, i.e., 7 etc. If we want to make this process easy, then we can use a queue to store the vertex or node, and we will mark it as visited until all its neighbors are marked. The advantage of using a queue is, queue works on the First in First out rule, which is quite important in the traversing. So, we can say that we will visit the node in which they were added in the queue like, a node is inserted first in the queue, so we will visit it first.
Algorithm of Breadth First Search: -
BFS (G, S) //Where S is the Root node or source node and G is the graph. Let Q be a queue. Q.add( S ) // We will s in to queue mark S as visited. while ( Q is not empty) //We will remove the vertax from the queue v = Q.remove( ) // Traversing the all neighbor of v for all the neighbors w of v in Graph G if w is not visited Q.add( w ) //we will store w in the Q mark w as visited.
Traversing Process: -
In this, we will start traversing from source node and we will push s in the queue, then we will mark it as ‘visited’.
First iteration:
- We will pop s from the queue
- So, we need to traverse of s Neighbors, i.e., 23 and 37
- The vertex 23 and 37 didn’t traverse earlier, are traversed. They will be:
- Pushed in the queue
- We will mark 23 and 37 as visited
Second iteration:
- We will pop 23 from the queue
- Neighbors of 23, i.e., s and 20 are traversed
- We will ignore s because it is marked as 'visited'
- The vertex 20 didn’t traverse earlier, is traversed. It is:
- Pushed in the queue
- Marked as visited
Third iteration:
- We will pop 37 from the queue
- Neighbors of 37, i.e., s, 20, and 73 are traversed
- 20 and s both are already ‘visited’ so we will ignore them.
- The vertex 20 didn’t traverse earlier, is traversed. It is:
- Pushed in the queue
- Marked as visited
Fourth iteration:
- We will pop 20 from the queue
- Neighbors of 20, i.e., 23, 37, and 30 are traversed
- 23 and 37 both are already ‘visited’ so we will ignore them.
- The vertex 30 didn’t traverse earlier, is traversed. It is:
- Pushed in the queue
- Marked as visited
Fifth iteration:
- We will pop 73 from the queue
- Neighbors of 73, i.e., 37 is traversed
- The vertex 37 already has visited so we will ignore it
Sixth iteration:
- We will pop 30 from the queue
- Neighbors of 30, i.e., 20 is traversed
- The vertex 20 already has visited so we will ignore it
The queue is empty and it comes out of the loop. All the nodes have been traversed by using BFS.
Implementation of BFS in C language: -
#include <stdio.h>
#include <stdlib.h>
#define LEN 40
struct queue {
int data[LEN];
int start;
int end;
};
struct queue * createQueue();
void add(struct queue * q, int);
int del(struct queue * q);
int isEmpty(struct queue * q);
void traverse(struct queue * q);
struct node {
int vertex;
struct node* next;
};
struct node * create_Node(int);
struct Graph {
int numVertices;
struct node ** adjLists;
int* visited;
};
// Algorithm of BFS
void bfs(struct Graph * graph, int startVertex) {
struct queue * q = createQueue();
graph -> visited[startVertex] = 1;
add(q, startVertex);
while (!isEmpty(q)) {
traverse(q);
int current_Vertex = del(q);
printf("Visited %d\n", current_Vertex);
struct node * temp = graph -> adjLists[current_Vertex];
while (temp) {
int adjVertex = temp -> vertex;
if (graph -> visited[adjVertex] == 0) {
graph -> visited[adjVertex] = 1;
add(q, adjVertex);
}
temp = temp -> next;
}
}
}
// Creating a node
struct node * create_Node(int v) {
struct node * newNode = malloc(sizeof(struct node));
newNode -> vertex = v;
newNode -> next = NULL;
return newNode;
}
// Creating a graph
struct Graph * createGraph(int vertices) {
struct Graph * graph = malloc(sizeof(struct Graph));
graph -> numVertices = vertices;
graph -> adjLists = malloc(vertices * sizeof(struct node *));
graph -> visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph -> adjLists[i] = NULL;
graph -> visited[i] = 0;
}
return graph;
}
// Add edge
void adding_Edge(struct Graph * graph, int src, int dest) {
// Add edge from source to destination
struct node * newNode = create_Node(dest);
newNode -> next = graph -> adjLists[src];
graph -> adjLists[src] = newNode;
// Add edge from dest to src
newNode = create_Node(src);
newNode -> next = graph -> adjLists[dest];
graph -> adjLists[dest] = newNode;
}
// Creating a queue
struct queue * createQueue() {
struct queue * q = malloc(sizeof(struct queue));
q -> start = -1;
q -> end = -1;
return q;
}
// Check queue is empty or not
int isEmpty(struct queue * q) {
if (q -> end == -1)
return 1;
else
return 0;
}
// Adding elements into queue
void add(struct queue * q, int value) {
if (q -> end == LEN - 1)
printf("\nQueue is Full!!");
else {
if (q -> start == -1)
q -> start = 0;
q -> end++;
q -> data[q -> end] = value;
}
}
// Deleting elements from queue
int del(struct queue * q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
}
else {
item = q -> data[q -> start];
q -> start++;
if (q -> start > q -> end) {
printf("Resetting queue ");
q -> start = q -> end = -1;
}
}
return item;
}
// Print the queue
void traverse(struct queue * q) {
int i = q -> start;
if (isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains \n");
for (i = q -> start; i < q -> end + 1; i++) {
printf("%d ", q -> data[i]);
}
}
}
int main() {
struct Graph * graph = createGraph(6);
adding_Edge(graph, 0, 1);
adding_Edge(graph, 0, 2);
adding_Edge(graph, 1, 2);
adding_Edge(graph, 1, 4);
adding_Edge(graph, 1, 3);
adding_Edge(graph, 2, 4);
adding_Edge(graph, 3, 4);
bfs(graph, 0);
return 0;
}
Output: -
The complexity of Breadth First Search: -
If we talk about the time complexity of breadth first search is O(V+E), where V is the number of nodes in a graph and E is the number of edges in the graph and the space complexity is O(v).
Applications: -
- BFS is used in GPS navigation
- It is used to find the minimum spanning tree
- It is used for cycle detection in the undirected graph
- It is used in network algorithms