Breadth First Search (BFS) is a graph traversal algorithm that visits nodes level by level using a queue (FIFO). It is commonly used to find the shortest path in an unweighted graph.
Key Points (Quick Revision)
- BFS uses a Queue (FIFO)
- It visits nodes level by level
- It guarantees the shortest path (unweighted graph)
- Time Complexity: O(V + E)
- Space Complexity: O(V)
BFS in Very Simple Words
BFS is like spreading out step by step.
- Start from one node
- Visit all nearby nodes first
- Then go to the next level
It works like a wave or circle expansion.
Real-Life Example
Think of:
- Spreading news in a group
- Water waves after dropping a stone
- Fire spreading in a forest
First nearby → then next → then next. This is exactly how BFS works.
Example Graph
0
/ \
1 2
/ \
3 4
BFS Output:
0 → 1 → 2 → 3 → 4
How BFS Works (Step-by-Step)
- Start from a node
- Add it to the queue
- Mark it as visited
- Remove from queue
- Visit all neighbors
- Add unvisited neighbors to the queue
- Repeat
Algorithm (Simple Version)
Start node
→ Add to queue
→ While queue is not empty:
- Remove node
- Print node
- Add all unvisited neighbors
Java Code – BFS using Adjacency List
import java.util.*;
public class BFSGraph {
int vertices;
LinkedList<Integer>[] list;
public BFSGraph(int v) {
vertices = v;
list = new LinkedList[v];
for (int i = 0; i < v; i++) {
list[i] = new LinkedList<>();
}
}
public void addEdge(int source, int destination) {
list[source].add(destination);
list[destination].add(source); // undirected
}
public void bfs(int start) {
boolean[] visited = new boolean[vertices];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : list[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
BFSGraph g = new BFSGraph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
System.out.print("BFS Traversal: ");
g.bfs(0);
}
}
When to Use BFS
Use BFS when:
- You need the shortest path (unweighted graph)
- You want level-by-level traversal
- You are solving minimum steps problems
- You are working with networks or connections
Applications of BFS
- Shortest path (unweighted graph)
- Social network connections
- Web crawling
- GPS systems
- Network broadcasting
BFS vs DFS (Simple Difference)
| BFS | DFS |
|---|---|
| Level by level | Depth first |
| Uses Queue | Uses Stack |
| Finds shortest path | No guarantee |
| Wider search | Deeper search |
Mini Quiz
Mini Project
Mini Project: Company Communication Network using BFS
Question:
A company wants to check how a message spreads from one employee to others through their communication network.
Create a Java program to:
- Create a graph using an Adjacency List.
- Add communication links between employees.
- Perform Breadth First Search (BFS) starting from employee 0.
- Display the order in which employees receive the message.
View Answer Code
import java.util.*;
public class CompanyNetworkBFS {
int vertices;
LinkedList<Integer>[] list;
// Constructor
public CompanyNetworkBFS(int v) {
vertices = v;
list = new LinkedList[v];
for (int i = 0; i < v; i++) {
list[i] = new LinkedList<>();
}
}
// Add communication link
public void addEdge(int source, int destination) {
list[source].add(destination);
list[destination].add(source);
}
// BFS Traversal
public void bfs(int start) {
boolean[] visited = new boolean[vertices];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int employee = queue.poll();
System.out.print(employee + " ");
for (int neighbor : list[employee]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
CompanyNetworkBFS company = new CompanyNetworkBFS(5);
company.addEdge(0, 1);
company.addEdge(0, 2);
company.addEdge(1, 3);
company.addEdge(1, 4);
System.out.print("Message Spread Order: ");
company.bfs(0);
}
}
FAQ – Direct Questions & Answers
What is BFS in Data Structures?
BFS is a graph traversal algorithm that visits nodes level by level using a queue.
Which data structure is used in BFS?
A queue (FIFO) is used in BFS.
What is BFS used for?
BFS is used for shortest path, graph traversal, and network problems.
What is the time complexity of BFS?
Time Complexity of BFS is O(V + E).
Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.
Shubhranshu Shekhar is a coding instructor, mentor, and founder of VSIT Delhi with 20+ years of teaching experience (since 2004). He has guided many students who are now working in multinational companies and specializes in Full Stack Development, Python, Digital Marketing, and Data Analytics.