Breadth-First Search (BFS)
Last updated
Breadth-first search explores a graph level by level. Starting from a source node, it visits all of its immediate neighbors first, then all of their unvisited neighbors, and so on - expanding outward in rings of increasing distance. Press play above to watch it fan out from the start node one layer at a time.
BFS uses a first-in-first-out queue, which is what enforces the level-by-level order. Because it reaches nodes in order of hop distance, BFS finds the shortest path (fewest edges) in an unweighted graph. It visits every node and edge once, so it runs in O(V + E) time.
Time & space complexity
| Measure | Complexity | Notes |
|---|---|---|
| Time | O(V + E) | Every vertex and edge visited once |
| Space | O(V) | Queue + visited set, worst case all nodes |
| Traversal | Level by level | Nearest nodes first, in rings |
| Shortest path | Yes (unweighted) | Reaches each node by fewest edges |
Step by step
| Step | What happens |
|---|---|
| 1 | Enqueue the source node. |
| 2 | Dequeue the front node and mark it visited. |
| 3 | Look at each of its neighbors. |
| 4 | Enqueue any neighbor not already visited or queued. |
| 5 | Repeat until the queue is empty. |
Worked example
Traversing this graph from node 0, where 0-1, 0-2, 1-3, 2-3, 2-4 are edges:
| Step | Visited | Queue (frontier) |
|---|---|---|
| Start | {} | [0] |
Dequeue 0 | {0} | [1, 2] |
Dequeue 1 | {0, 1} | [2, 3] |
Dequeue 2 | {0, 1, 2} | [3, 4] |
Dequeue 3 | {0, 1, 2, 3} | [4] |
Dequeue 4 | {0, 1, 2, 3, 4} | [] (done) |
When to use BFS
| Use it when | Avoid it when |
|---|---|
| You need the shortest path in an unweighted graph | Edges have weights - use Dijkstra instead |
| The target is likely close to the source | The graph is very wide - the queue can hold a huge frontier |
| You want to explore a graph in level order | You only need to reach any node, where DFS uses less memory |
| You are finding connected components or a minimum-hop route | You need topological sorting or cycle detection - DFS fits better |
Breadth-First Search code
A clean, runnable Breadth-First Search implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Breadth-First Search code in Python
Python
1from collections import deque2
3
4def bfs(graph, start):5 visited = {start}6 queue = deque([start])7 order = []8 while queue:9 node = queue.popleft()10 order.append(node)11 for neighbor in graph[node]:12 if neighbor not in visited:13 visited.add(neighbor) # mark on enqueue, not dequeue14 queue.append(neighbor)15 return order16
17
18graph = {19 "A": ["B", "C"],20 "B": ["D", "E"],21 "C": ["F"],22 "D": [],23 "E": ["F"],24 "F": [],25}26
27print("BFS order:", " -> ".join(bfs(graph, "A")))Breadth-First Search code in JavaScript
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function bfs(start) {11 const visited = new Set([start]);12 const queue = [start];13 const order = [];14 while (queue.length > 0) {15 const node = queue.shift(); // Dequeue the oldest node16 order.push(node);17 for (const next of graph[node]) {18 if (!visited.has(next)) {19 visited.add(next);20 queue.push(next);21 }22 }23 }24 return order;25}26
27console.log("BFS from A:", bfs("A").join(" -> "));Breadth-First Search code in Java
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 List<List<Integer>> adj = List.of(8 List.of(1, 2), // neighbors of 09 List.of(0, 3, 4), // neighbors of 110 List.of(0, 5),11 List.of(1),12 List.of(1, 5),13 List.of(2, 4)14 );15 boolean[] visited = new boolean[adj.size()];16 Queue<Integer> queue = new ArrayDeque<>();17 visited[0] = true;18 queue.add(0);19
20 StringBuilder order = new StringBuilder("BFS from 0:");21 while (!queue.isEmpty()) {22 int node = queue.poll();23 order.append(" ").append(node);24 // Mark neighbors when enqueued so nothing enters twice25 for (int next : adj.get(node)) {26 if (!visited[next]) {27 visited[next] = true;28 queue.add(next);29 }30 }31 }32 System.out.println(order);33 }34}Breadth-First Search code in C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5void bfs(int start, const std::vector<std::vector<int>>& adj) {6 std::vector<bool> visited(adj.size(), false);7 std::queue<int> frontier;8 visited[start] = true;9 frontier.push(start);10 // Visit nodes level by level11 while (!frontier.empty()) {12 int node = frontier.front();13 frontier.pop();14 std::cout << node << " ";15 for (int next : adj[node]) {16 if (!visited[next]) {17 visited[next] = true;18 frontier.push(next);19 }20 }21 }22}23
24int main() {25 // 6-node undirected graph as an adjacency list26 std::vector<std::vector<int>> adj = {27 {1, 2}, // 028 {0, 3, 4}, // 129 {0, 5}, // 230 {1}, // 331 {1, 5}, // 432 {2, 4}, // 533 };34 std::cout << "BFS from node 0: ";35 bfs(0, adj);36 std::cout << "\n";37 return 0;38}Breadth-First Search code in C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6void bfs(int start, const int adj[N][N]) {7 bool visited[N] = {false};8 int queue[N]; // fixed-size queue: head chases tail9 int head = 0, tail = 0;10 visited[start] = true;11 queue[tail++] = start;12 // Visit nodes level by level13 while (head < tail) {14 int node = queue[head++];15 printf("%d ", node);16 for (int next = 0; next < N; next++) {17 if (adj[node][next] && !visited[next]) {18 visited[next] = true;19 queue[tail++] = next;20 }21 }22 }23}24
25int main(void) {26 // 6-node undirected graph as an adjacency matrix27 int adj[N][N] = {28 {0, 1, 1, 0, 0, 0},29 {1, 0, 0, 1, 1, 0},30 {1, 0, 0, 0, 0, 1},31 {0, 1, 0, 0, 0, 0},32 {0, 1, 0, 0, 0, 1},33 {0, 0, 1, 0, 1, 0},34 };35 printf("BFS from node 0: ");36 bfs(0, adj);37 printf("\n");38 return 0;39}Breadth-First Search FAQ
What is the time complexity of BFS?
BFS runs in
O(V + E) time, where V is the number of vertices and E the number of edges, since it visits each vertex once and examines each edge once. It uses O(V) space for the queue and visited set.Does BFS find the shortest path?
Yes, in an unweighted graph. Because BFS reaches nodes in order of hop distance from the source, the first time it reaches a node is along a path with the fewest edges. For weighted graphs you need Dijkstra's algorithm instead.
What is the difference between BFS and DFS?
BFS uses a queue and explores level by level (nearest first), while DFS uses a stack and dives deep along one branch before backtracking. BFS finds shortest unweighted paths; DFS uses less memory on wide graphs and suits cycle detection and topological sorting.
When should I use BFS instead of Dijkstra's algorithm?
Use BFS when every edge has the same cost, because it finds the fewest-edge path in
O(V + E) time without a priority queue. Dijkstra's algorithm is needed when edges carry different weights; running plain BFS on a weighted graph gives the shortest-hop path, not the lowest-cost one.Why does BFS need a visited set?
Graphs can contain cycles, so without a visited set BFS would enqueue the same node repeatedly and loop forever. Marking a node when you first enqueue it (not when you dequeue it) also prevents the same node from being added to the queue twice by different neighbors.
Should I mark a node visited when enqueuing or dequeuing it?
Mark it when you enqueue it. If you wait until you dequeue it, a node can be added to the queue multiple times by different neighbors before it is processed, wasting memory and time. Marking on enqueue guarantees each node enters the queue exactly once.
Related resources
More visualizations
