What is BFS
BFS is a breadth-first Search (BFS), Imagine you are trying to find your way through a maze, and you want to find the shortest path from your starting point to the exit. You can think of BFS as a method that helps you explore the maze systematically, step by step, until you reach your goal.
Here's how BFS works in simple terms:
1. You start at your current position (the starting point) and examine all the paths (neighbors) connected to it.
2. You then move to each of those neighboring paths and examine their neighbors, but you don't go too deep just yet. You focus on exploring all the paths at the same distance from your starting point first.
3. Once you have examined all the neighbors of your starting point, you move on to the next level of paths. These are the paths that are one step away from your starting point.
4. You repeat this process, examining all the neighbors at each level, moving to the next level, until you find the exit or reach your goal.
The important thing to note about BFS is that it explores the maze layer by layer, making sure to check all the paths at each distance from the starting point before moving deeper into the maze. This guarantees that if there is a path to the exit, BFS will find the shortest one.
To summarize, BFS is like exploring a maze by checking all the possible paths at each distance from your starting point before moving deeper. It helps you find the shortest path to your destination by systematically searching the available options.
Who invented it?
Breadth-First Search (BFS) is a fundamental graph traversal algorithm that has been around for quite some time. The precise origins of BFS are not attributed to a single person or inventor.
The concept of BFS can be traced back to the late 19th century when mathematicians and computer scientists started studying graph theory. The algorithm itself evolved over time and became widely known and used in various fields, including computer science, mathematics, and operations research.
Notably, BFS was formalized and popularized by a mathematician named Charles E. Leiserson in his book "Introduction to Algorithms," co-authored with Thomas H. Cormen, Ronald L. Rivest, and Clifford Stein. This book, commonly known as "CLRS," has been influential in the field of algorithms and data structures, and it played a significant role in disseminating knowledge about BFS and other important algorithms.
Pseudocode
BFS(graph, start):
queue = empty queue
visited = empty set
enqueue(queue, start)
add start to visited
while queue is not empty:
current = dequeue(queue)
process current (e.g., check if it's the goal)
for each neighbor in graph.neighbors(current):
if neighbor is not in visited:
add neighbor to visited
enqueue(queue, neighbor)
In this pseudocode, graph represents the graph or maze you want to search, start represents the starting point, and graph.neighbors(current) represents a function that returns the neighbors of a given node current.
The algorithm uses a queue data structure to keep track of the nodes to explore. It starts by adding the starting node to the queue and marks it as visited. Then, it enters a loop that continues until the queue is empty. Within the loop, it dequeues the current node from the front of the queue, processes it (e.g., checks if it's the goal), and explores its neighbors. If a neighbor has not been visited before, it adds it to the visited set and enqueues it to be processed later.
This process continues until the queue is empty or until the goal is found. BFS ensures that nodes are explored in a breadth-first manner, meaning that it visits all the neighbors of a node before moving on to their neighbors. This guarantees that if there is a path to the goal, BFS will find the shortest path.
The algorithm uses a queue data structure to keep track of the nodes to explore. It starts by adding the starting node to the queue and marks it as visited. Then, it enters a loop that continues until the queue is empty. Within the loop, it dequeues the current node from the front of the queue, processes it (e.g., checks if it's the goal), and explores its neighbors. If a neighbor has not been visited before, it adds it to the visited set and enqueues it to be processed later.
This process continues until the queue is empty or until the goal is found. BFS ensures that nodes are explored in a breadth-first manner, meaning that it visits all the neighbors of a node before moving on to their neighbors. This guarantees that if there is a path to the goal, BFS will find the shortest path.
Sample Code
// C++ code snippet
using namespace std;
// Function to perform BFS
void BFS(vector < vector < int > >& graph, int start) {
int numVertices = graph.size();
vector visited(numVertices, false);
// Create a queue for BFS
queue < int > q;
// Mark the current node as visited and enqueue it
visited[start] = true;
q.push(start);
while (!q.empty()) {
// Dequeue a vertex from the queue and print it
int current = q.front();
cout << current << " ";
q.pop();
// Get all adjacent vertices of the dequeued vertex
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
// Mark the neighbor as visited and enqueue it
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
// Driver code
int main() {
// Create a graph using adjacency list
vector < vector < int > > graph = {
{1, 2}, // Node 0 is connected to nodes 1 and 2
{0, 2, 3}, // Node 1 is connected to nodes 0, 2, and 3
{0, 1, 3}, // Node 2 is connected to nodes 0, 1, and 3
{1, 2, 4}, // Node 3 is connected to nodes 1, 2, and 4
{3} // Node 4 is connected to node 3
};
int startNode = 0; // Starting node for BFS
cout << "BFS Traversal: ";
BFS(graph, startNode);
cout << endl;
return 0;
}
# Python code snippet
from collections import deque
# Function to perform BFS
def BFS(graph, start):
numVertices = len(graph)
visited = [False] * numVertices
# Create a queue for BFS
queue = deque()
# Mark the current node as visited and enqueue it
visited[start] = True
queue.append(start)
while queue:
# Dequeue a vertex from the queue and print it
current = queue.popleft()
print(current, end=" ")
# Get all adjacent vertices of the dequeued vertex
for neighbor in graph[current]:
if not visited[neighbor]:
# Mark the neighbor as visited and enqueue it
visited[neighbor] = True
queue.append(neighbor)
# Driver code
if __name__ == "__main__":
# Create a graph using adjacency list
graph = [
[1, 2], # Node 0 is connected to nodes 1 and 2
[0, 2, 3], # Node 1 is connected to nodes 0, 2, and 3
[0, 1, 3], # Node 2 is connected to nodes 0, 1, and 3
[1, 2, 4], # Node 3 is connected to nodes 1, 2, and 4
[3] # Node 4 is connected to node 3
]
startNode = 0 # Starting node for BFS
print("BFS Traversal:", end=" ")
BFS(graph, startNode)
print()
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
// Class representing a graph
class Graph {
private int numVertices;
private ArrayList> adjacencyList;
// Constructor
Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
// Function to add an edge to the graph
void addEdge(int source, int destination) {
adjacencyList.get(source).add(destination);
}
// Function to perform BFS
void BFS(int start) {
boolean[] visited = new boolean[numVertices];
// Create a queue for BFS
Queue queue = new LinkedList<>();
// Mark the current node as visited and enqueue it
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
// Dequeue a vertex from the queue and print it
int current = queue.poll();
System.out.print(current + " ");
// Get all adjacent vertices of the dequeued vertex
for (int neighbor : adjacencyList.get(current)) {
if (!visited[neighbor]) {
// Mark the neighbor as visited and enqueue it
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
}
// Main class
public class Main {
public static void main(String[] args) {
// Create a graph
Graph graph = new Graph(5);
// Add edges to the graph
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
int startNode = 0; // Starting node for BFS
System.out.print("BFS Traversal: ");
graph.BFS(startNode);
System.out.println();
}
}