BFS Breadth First Search
In this page:
What is BFS
Breadth-first search (BFS) explores a graph level by level, visiting all of a vertex's direct neighbors before moving on to their neighbors — this level-by-level order is what guarantees it finds the shortest path in terms of number of edges.
Example: What is BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
queue<int> q; vector<bool> visited(4,false);
q.push(0); visited[0]=true;
cout << "Level order from 0: ";
while (!q.empty()) {
int u = q.front(); q.pop(); cout << u << " ";
for (int v : adj[u]) if (!visited[v]) { visited[v]=true; q.push(v); }
}
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[4];
q.add(0); visited[0] = true;
System.out.print("Level order from 0: ");
while (!q.isEmpty()) {
int u = q.poll(); System.out.print(u + " ");
for (int v : adj.get(u)) if (!visited[v]) { visited[v] = true; q.add(v); }
}
}
}from collections import deque
adj = [[1,2],[0,3],[0,3],[1,2]]
visited = [False]*4
q = deque([0]); visited[0] = True
print("Level order from 0:", end=" ")
while q:
u = q.popleft()
print(u, end=" ")
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)#include <stdio.h>
int main() {
int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
int queue[4], front=0, back=0, visited[4]={0};
queue[back++]=0; visited[0]=1;
printf("Level order from 0: ");
while (front < back) {
int u = queue[front++];
printf("%d ", u);
for (int i = 0; i < 2; i++) {
int v = adj[u][i];
if (!visited[v]) { visited[v]=1; queue[back++]=v; }
}
}
return 0;
}Login to try C/C++/Java code in the editor
Queue in BFS
A queue drives the traversal: start by enqueuing the source vertex, then repeatedly dequeue a vertex, process it, and enqueue any of its unvisited neighbors — because the queue is first-in-first-out, vertices are naturally processed in order of distance from the source.
Example: Queue in BFS
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(5); q.push(3); q.push(8);
cout << "First out (FIFO): " << q.front();
q.pop();
cout << ", next: " << q.front();
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.add(5); q.add(3); q.add(8);
System.out.print("First out (FIFO): " + q.poll());
System.out.println(", next: " + q.peek());
}
}from collections import deque
q = deque([5, 3, 8])
first = q.popleft()
print(f"First out (FIFO): {first}, next: {q[0]}")#include <stdio.h>
int main() {
int queue[3] = {5, 3, 8}, front = 0;
int firstOut = queue[front++];
printf("First out (FIFO): %d, next: %d", firstOut, queue[front]);
return 0;
}Login to try C/C++/Java code in the editor
Visited Array
A visited array (or set) marks each vertex the moment it's enqueued, preventing it from being added to the queue again later through a different path — without this, BFS could process the same vertex repeatedly and never terminate on a graph with cycles.
Example: Visited Array
#include <iostream>
using namespace std;
int main() {
bool visited[5] = {false};
int vertex = 2;
if (!visited[vertex]) { visited[vertex] = true; cout << vertex << " marked visited, enqueued once"; }
if (visited[vertex]) cout << " -- re-enqueue attempt skipped";
return 0;
}public class Main {
public static void main(String[] args) {
boolean[] visited = new boolean[5];
int vertex = 2;
if (!visited[vertex]) { visited[vertex] = true; System.out.print(vertex + " marked visited, enqueued once"); }
if (visited[vertex]) System.out.print(" -- re-enqueue attempt skipped");
}
}visited = [False] * 5
vertex = 2
if not visited[vertex]:
visited[vertex] = True
print(f"{vertex} marked visited, enqueued once", end="")
if visited[vertex]:
print(" -- re-enqueue attempt skipped")#include <stdio.h>
int main() {
int visited[5] = {0};
int vertex = 2;
if (!visited[vertex]) { visited[vertex] = 1; printf("%d marked visited, enqueued once", vertex); }
if (visited[vertex]) printf(" -- re-enqueue attempt skipped");
return 0;
}Login to try C/C++/Java code in the editor
BFS Uses
Because BFS explores strictly in order of increasing distance from the source, it's the standard tool for finding shortest paths in unweighted graphs — the first time a vertex is reached is guaranteed to be via a shortest possible path.
Example: BFS Uses
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
vector<int> dist(4, -1);
queue<int> q; q.push(0); dist[0] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u]+1; q.push(v); }
}
cout << "Shortest hops from 0 to 3: " << dist[3];
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
int[] dist = {0,-1,-1,-1};
Queue<Integer> q = new LinkedList<>(); q.add(0);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) if (dist[v] == -1) { dist[v] = dist[u]+1; q.add(v); }
}
System.out.println("Shortest hops from 0 to 3: " + dist[3]);
}
}from collections import deque
adj = [[1,2],[0,3],[0,3],[1,2]]
dist = [-1]*4
dist[0] = 0
q = deque([0])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
print("Shortest hops from 0 to 3:", dist[3])#include <stdio.h>
int main() {
int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
int dist[4] = {0,-1,-1,-1}, queue[4], front=0, back=0;
queue[back++] = 0;
while (front < back) {
int u = queue[front++];
for (int i = 0; i < 2; i++) {
int v = adj[u][i];
if (dist[v] == -1) { dist[v] = dist[u]+1; queue[back++] = v; }
}
}
printf("Shortest hops from 0 to 3: %d", dist[3]);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
With an adjacency list, BFS runs in O(V + E) time, since every vertex is enqueued once and every edge is examined once across the whole traversal — this linear-in-graph-size behavior is what makes BFS practical even on fairly large graphs.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once");
}
}print("BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once")#include <stdio.h>
int main() {
printf("BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: