BFS Breadth First Search Algorithm is an important DAA topic because it appears in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.
For this page, focus on what problem BFS Breadth First Search Algorithm solves, where developers usually make mistakes, and how to verify the result. The audit note for this lesson was: limited checklist/practice/mistake/FAQ notes .
A strong understanding of BFS Breadth First Search Algorithm should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work with tools or output.
BFS Breadth First Search Algorithm should be studied as a practical algorithm analysis lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.
In the daa > bfs page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.
Breadth-First Search (BFS) is a graph traversal technique that explores vertices level by level. Starting from a source vertex, it first visits all vertices at distance 1, then all vertices at distance 2, and so on. BFS uses a queue, so the earliest discovered vertex is processed first.
BFS is the standard graph traversal technique when we care about distance in number of edges, level structure, or minimum hops. It is not just a way to visit nodes; it is the foundation of shortest path algorithms for unweighted graphs, level-order tree traversal, connected-component discovery, bipartite checking, and many grid-based search problems.
Think of BFS like a wave spreading in water. The source vertex is the point where the wave begins. In the first step, the wave touches all immediate neighbors. In the next step, it reaches the neighbors of those neighbors. Because BFS always processes the current layer completely before moving deeper, the first time we reach a vertex, we have found the minimum number of edges needed to get there.
| Concept | Meaning in BFS |
|---|---|
| Source vertex | Starting point of traversal |
| Visited array / set | Prevents processing the same vertex multiple times |
| Queue | Stores discovered vertices waiting to be processed |
| Level | All vertices at the same distance from the source |
| Parent array | Helps reconstruct the actual shortest path |
| Distance array | Stores number of edges from the source |
Consider the graph with edges: 0-1, 0-2, 1-3, 1-4, 2-5. Start BFS from vertex 0.
BFS order: 0, 1, 2, 3, 4, 5. Distances from 0: dist[0]=0, dist[1]=1, dist[2]=1, dist[3]=2, dist[4]=2, dist[5]=2.
| Step | Queue Before | Process | Queue After | Visited So Far |
|---|---|---|---|---|
| 1 | [0] | Dequeue 0, discover 1 and 2 | [1, 2] | 0, 1, 2 |
| 2 | [1, 2] | Dequeue 1, discover 3 and 4 | [2, 3, 4] | 0, 1, 2, 3, 4 |
| 3 | [2, 3, 4] | Dequeue 2, discover 5 | [3, 4, 5] | 0, 1, 2, 3, 4, 5 |
| 4 | [3, 4, 5] | Dequeue 3, no new neighbor | [4, 5] | unchanged |
| 5 | [4, 5] | Dequeue 4, no new neighbor | [5] | unchanged |
| 6 | [5] | Dequeue 5, no new neighbor | [] | unchanged |
As BFS runs, it forms a BFS tree. Each newly discovered vertex gets a parent, and all vertices discovered from the same distance belong to the same level.
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); // undirected graph
}
// BFS traversal - O(V + E)
static void bfs(int src) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[src] = true;
queue.offer(src);
System.out.print("BFS order: ");
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
System.out.println();
}
// Shortest path distances in an unweighted graph
static int[] shortestPath(int src) {
int[] dist = new int[V];
Arrays.fill(dist, -1);
Queue<Integer> queue = new LinkedList<>();
dist[src] = 0;
queue.offer(src);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
queue.offer(neighbor);
}
}
}
return dist;
}
public static void main(String[] args) {
buildGraph(6);
addEdge(0, 1); addEdge(0, 2);
addEdge(1, 3); addEdge(1, 4);
addEdge(2, 5);
bfs(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]);
}
}
}In an unweighted graph, every edge contributes the same cost: one step. BFS explores all vertices reachable in 1 step before any vertex reachable in 2 steps, all vertices reachable in 2 steps before any vertex reachable in 3 steps, and so on. Therefore, when a vertex is discovered for the first time, BFS has already found the minimum number of edges from the source to that vertex.
To recover the actual shortest path, we store a parent for each vertex when it is first discovered.
This is useful because BFS itself tells us both the minimum distance and the structure of the shortest path tree.
If the graph is disconnected, a BFS starting from one source visits only the connected component containing that source. To traverse the whole graph, we repeat BFS from every unvisited vertex.
Sometimes we need the distance from the nearest source among several starting points. In that case, we can begin BFS with all sources already in the queue and distance 0 for each of them. This is called multi-source BFS.
It is common in problems like nearest hospital, nearest exit, nearest zero in a matrix, and spreading processes such as fire, infection, or signal propagation.
A graph is bipartite if its vertices can be split into two groups such that no edge connects vertices in the same group. BFS helps by coloring alternate levels with opposite colors.
| Measure | Value | Reason |
|---|---|---|
| Time complexity | O(V + E) | Every vertex is enqueued once and every edge is examined once |
| Space complexity | O(V) | Visited array, distance array, parent array, and queue |
| Best graph representation | Adjacency list | Efficient neighbor iteration |
BFS works for shortest path only when every edge has equal cost. If one edge has weight 10 and another has weight 1, the path with fewer edges may not be the cheapest path. That is why weighted graphs need algorithms like Dijkstra or Bellman-Ford.
| Feature | BFS | DFS |
|---|---|---|
| Traversal style | Level by level | Go deep, then backtrack |
| Main data structure | Queue | Stack / recursion |
| Shortest path in unweighted graph | Yes | No guarantee |
| Useful for | Distance, layers, minimum hops | Cycle detection, topological sort, backtracking |
1. Write the input for BFS Breadth First Search Algorithm.
2. Trace each decision step by step.
3. Count the operations that dominate runtime.
4. Test an edge case and compare the result.1. Try empty, missing, duplicate, or invalid data.
2. Identify where BFS Breadth First Search Algorithm changes behavior.
3. Explain the safest correction.
4. Retest the normal path.Memorizing BFS Breadth First Search Algorithm without the situation where it is useful.
Connect BFS Breadth First Search Algorithm to a concrete algorithm analysis task.
Testing BFS Breadth First Search Algorithm only with the perfect input.
Include empty, missing, duplicate, incompatible, or failed cases when relevant.
Changing code before reading the visible symptom or error message.
Inspect the output, state, configuration, or stack trace connected to BFS Breadth First Search Algorithm.
Memorizing BFS Breadth First Search Algorithm without the situation where it is useful.
Connect BFS Breadth First Search Algorithm to a concrete algorithm analysis task.
The common mistake is memorizing syntax without understanding when the behavior changes or fails.
Remember the problem it solves in algorithm analysis, then attach the syntax or steps to that problem.
You can predict the result of a small example, explain a failure case, and choose it over a nearby alternative for a clear reason.
They often copy the syntax but skip the state, input, dependency, selector, route, type, or configuration that controls the behavior.
Explore 500+ free tutorials across 20+ languages and frameworks.