Breadth-First Search (BFS)
What is BFS?
Breadth-First Search (BFS) explores a graph level by level — it visits all neighbors of a vertex before moving to the next level. It uses a queue (FIFO) to track which vertex to visit next.
- Finds the shortest path in an unweighted graph
- Explores all vertices at distance k before any vertex at distance k+1
- Time: O(V + E), Space: O(V)
import java.util.*;
public class BFS {
static int V;
static List<List<Integer>> adj;
static void buildGraph(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
}
static void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u);
}
// BFS traversal from source — O(V + E)
static void bfs(int src) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[src] = true;
queue.add(src);
System.out.print("BFS from " + src + ": ");
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
System.out.println();
}
// Shortest path (unweighted) using BFS
static int[] shortestPath(int src) {
int[] dist = new int[V];
Arrays.fill(dist, -1);
Queue<Integer> queue = new LinkedList<>();
dist[src] = 0;
queue.add(src);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
queue.add(neighbor);
}
}
}
return dist;
}
public static void main(String[] args) {
buildGraph(6);
addEdge(0, 1); addEdge(0, 2);
addEdge(1, 3); addEdge(2, 4);
addEdge(3, 5); addEdge(4, 5);
bfs(0); // BFS from 0: 0 1 2 3 4 5
int[] dist = shortestPath(0);
System.out.println("Shortest distances from 0:");
for (int i = 0; i < V; i++) {
System.out.println(" to " + i + ": " + dist[i]);
}
}
}
/*
* Graph:
* 0 - 1 - 3 - 5
* | | |
* 2 - 4 --+---+
*
* BFS order: 0, 1, 2, 3, 4, 5
* Distances from 0: 0→0, 1→1, 2→1, 3→2, 4→2, 5→3
*/BFS Applications
- Shortest path in unweighted graphs (each edge has weight 1)
- Level-order traversal of trees
- Connected components — find all vertices reachable from a source
- Bipartite graph check — can vertices be colored with 2 colors?
- Web crawling — explore web pages level by level
- Social network — find friends within k degrees of separation
BFS — Level-by-Level Visualization
For graph: 0-1, 0-2, 1-3, 1-4, 2-5, starting BFS from vertex 0:
| Level | Vertices | Queue State |
|---|---|---|
| 0 | 0 | [0] → dequeue 0, enqueue neighbors 1, 2 |
| 1 | 1, 2 | [1, 2] → dequeue 1, enqueue 3, 4; dequeue 2, enqueue 5 |
| 2 | 3, 4, 5 | [3, 4, 5] → dequeue all, no unvisited neighbors |