# 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();
}
}

## Time and Space Complexity

The time and space complexity of the Breadth-First Search (BFS) algorithm depends on the size of the graph and the branching factor (average number of neighbors) of each node. Let's denote the number of vertices in the graph as V and the number of edges as E.

The time complexity of BFS is O(V + E), as it visits each vertex and each edge in the worst case. In the worst-case scenario, BFS needs to explore the entire graph to find the goal or reach all reachable nodes.

The space complexity of BFS is O(V), as it needs to store the visited nodes and the queue of nodes to be processed. In the worst case, the queue can contain all the nodes in the graph, which is bounded by the number of vertices V.

Therefore, the time complexity is linear with respect to the number of vertices and edges, and the space complexity is also linear with respect to the number of vertices in the graph.

## Advantages

1. Completeness: BFS is a complete algorithm, meaning that it will find a solution if one exists. It guarantees that it will find the shortest path to the goal if there is one.

2. Optimal Solution: If the graph is unweighted (all edges have the same weight), BFS will always find the optimal solution, i.e., the shortest path from the starting node to the goal.

3. Exploration of Nearby Nodes: BFS explores all the neighboring nodes of a given node before moving deeper into the graph. This characteristic makes it useful for tasks such as finding the shortest path, exploring a maze, or identifying all nodes reachable from a given node.

## Disadvantages

1. Memory Usage: BFS requires memory to store the visited nodes and the queue of nodes to be processed. In graphs with a large number of nodes, the memory requirement can be significant, especially if the graph is dense or has a high branching factor.

2. Inefficiency with Large Graphs: In graphs with a large number of nodes and edges, the time complexity of BFS can become impractical. Visiting all nodes and edges can be computationally expensive, especially if the graph is sparse or has a high average branching factor.

3. Lack of Heuristics: BFS does not take into account any heuristics or knowledge about the problem domain. It treats all edges equally and explores nodes solely based on their distance from the starting node. This can make BFS inefficient for certain types of problems where a heuristic-based search algorithm, such as A* search, would be more suitable.

It's important to consider the advantages and disadvantages of BFS based on the specific problem and graph characteristics to determine whether it is the most appropriate algorithm to use.