Breadth-First Search (BFS) is a graph traversal algorithm that starts traversing the graph from a specific node (the source or root node) and explores all the neighboring nodes at the present depth before moving on to nodes at the next depth level. It is often implemented using a queue data structure.
The basic idea behind BFS is as follows:
- Start with a source node and enqueue it into a queue.
- Dequeue a node from the queue and visit it.
- Enqueue all the neighboring nodes of the visited node that have not been visited yet.
- Mark the visited node as ‘visited.’
- If the queue is not empty, repeat steps 2-4; otherwise, the algorithm is finished.
Applications of BFS algorithm
Breadth-First Search (BFS) is a fundamental graph traversal algorithm that finds various applications in both theoretical computer science and real-world scenarios. Some of the key applications of BFS include:
- Finding Shortest Path in Unweighted Graphs: BFS can be used to find the shortest path between two nodes in an unweighted graph. Since BFS traverses the graph level by level, the first occurrence of the destination node guarantees the shortest path.
- Web Crawling: BFS is employed in web crawling to explore the web by starting from a particular webpage and following all the links on that page. It ensures that the pages closer to the starting page are visited first.
- Social Networking Websites: BFS can be used to find the degrees of separation between two people in a social network, helping to determine the path of connections between them.
- Garbage Collection: BFS is utilized in garbage collection algorithms to determine which objects are reachable and which are not, helping to identify and clean up unreachable objects.
- Finding Connected Components: BFS can be applied to find connected components in an undirected graph, helping to identify groups of nodes that are connected to each other.
- Finding the Minimum Spanning Tree: BFS can be utilized to find the minimum spanning tree in an unweighted graph. The minimum spanning tree is the subgraph that connects all the vertices together with the minimum possible total edge weight.
- Cyclic Graph Detection: BFS can be used to detect cycles in a graph. By maintaining a list of visited nodes during traversal, BFS can detect if there are any back edges while exploring the graph.
- Puzzle Solving and Maze Traversal: BFS is often employed to solve puzzles and traverse mazes, where the search space can be represented as a graph.
- Network Broadcast: BFS can be used in network communication protocols for broadcasting messages to all nodes in a network, ensuring that the messages propagate in an organized mann
Algorithm
The steps involved in the BFS algorithm to explore a graph are given as follows –
- Step 1: SET STATUS = 1 (ready state) for each node in G
- Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)
- Step 3: Repeat Steps 4 and 5 until QUEUE is empty
- Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).
Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS = 1) and set
their STATUS = 2
(waiting state)
[END OF LOOP]
- Step 6: EXIT
Example of BFS algorithm
Certainly, here is an example of the Breadth-First Search (BFS) algorithm in action. Suppose we have the following graph:
2
/ \
0 3
\
1
We can represent this graph using an adjacency list:
import java.util.*;
class Graph {
private int V;
private LinkedList<Integer> adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList();
}
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList<Integer> queue =
new LinkedList<Integer>();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll();
System.out.print(s + " ");
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(0, 1);
g.addEdge(3, 3);
System.out.println
("Following is Breadth First Traversal "
+ "(starting from vertex 2)");
g.BFS(2);
}
}
