15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Breadth first search (BFS) visits a graph in layers: the start vertex, then everything one edge away, then two edges away. It keeps discovered vertices in a FIFO queue and marks each one visited before enqueueing it. It runs in O(V + E) time with O(V) auxiliary space.
| Data structure | FIFO queue, plus a visited mark set at discovery |
|---|---|
| Time | O(V + E) |
| Auxiliary space | O(V) |
| Example from A | Order A, B, C, D; distances 0, 1, 1, 2 |
| Distance means | Edge count from the start; unreachable vertices stay at -1 |
The lesson assumes you can read graph terminology and an adjacency-list representation.
Use an adjacency list where each vertex’s neighbors appear in a stated order. That order determines the discovery order of breadth-first search, or BFS.
BFS starts at one vertex and explores outward in layers:
BFS uses a FIFO queue: the first vertex added is the first one removed.
BFS also needs a visited structure. Mark a vertex visited when it is discovered, before it enters the queue. This prevents the same vertex from entering the queue multiple times.
For a vertex v, distance(v) means the number of edges in the shortest discovered route from the start to v.
Use this adjacency-list graph. Neighbor order is left to right in each list.
1A: [B, C]
2B: [A, D]
3C: [A, D]
4D: [B, C]Run BFS from A.
The graph has these edges:
1 B
2 / \
3 A D
4 \ /
5 CBefore the loop begins:
A visited.distance(A) = 0.A into the queue.A as the first discovered vertex.1queue front -> [A] <- rear
2visited = {A}
3discovery order = [A]
4distance(A) = 0The layers come from edge count from A:
1layer 0: [A] distance 0
2layer 1: [B, C] distance 1
3layer 2: [D] distance 2A queue has a front and a rear. BFS removes from the front and appends newly discovered vertices at the rear.
BFS from A on the diamond: dequeue A and enqueue B, C at distance 1; dequeue B and enqueue D at distance 2; C and D add nothing. Order [A, B, C, D], layers [A], [B, C], [D].
A is the only known vertex, so it is the only vertex waiting to be processed.
Remove A from the front.
1current = A
2queue = []Inspect A’s neighbors in the supplied order: B, then C.
B is unvisited. Mark it visited, set distance(B) = 1, append it, and record it.C is unvisited. Mark it visited, set distance(C) = 1, append it, and record it.Both B and C are one edge from A. They enter the queue in adjacency-list order.
Remove B.
Inspect B’s neighbors in order: A, then D.
A is already visited. Do nothing.D is unvisited. Mark it visited before enqueueing it. Set distance(D) = distance(B) + 1 = 2. Append D.Remove C.
Inspect C’s neighbors: A, then D.
A is already visited.D is already visited. It was discovered from B.Do not enqueue either vertex.
Remove D.
1current = D
2queue = []Inspect D’s neighbors: B, then C.
Both are already visited, so neither enters the queue.
1queue = []
2visited = {A, B, C, D}
3order = [A, B, C, D]The queue is empty. No discovered vertex remains to process.
1BFS discovery order = [A, B, C, D]
2layers = [A], [B, C], [D]Two facts remain true throughout the loop:
An ordering fact also holds:
For example, B and C both have distance 1. They leave before D, which has distance 2.
The loop invariant is:
Every vertex in the queue is already marked visited and has a known shortest edge-count distance from the start. Vertices leave the FIFO queue in nondecreasing discovery distance.
Marking a vertex before enqueueing it makes the first part true. When B discovers D, D becomes visited immediately. Later, when C sees D, it does not add another copy of D.
Start with the requested start vertex.
-1, meaning “unreached.”0.Repeat while the queue is not empty:
current.current in the supplied adjacency order.current’s distance,When the queue becomes empty, every vertex reachable from the start has been processed. A vertex in a disconnected part of the graph was never discovered, so its distance remains -1.
adjacencyList is a mapping from each graph vertex to an ordered list of its neighbors.
adjacencyList.start must be a key in adjacencyList.start is absent, these functions report a validation failure.The functions do not mutate adjacencyList.
runBFS(adjacencyList, start) returns:
order: vertices in BFS discovery orderdistance: a mapping where reachable vertices have their edge-count distance from start, and unreachable vertices have -11function runBFS(adjacencyList, start):
2 input:
3 adjacencyList: mapping Vertex -> ordered list of Vertex
4 start: Vertex
5 returns:
6 (order, distance)
7 mutation:
8 does not modify adjacencyList
9
101. if start is not a key in adjacencyList:
112. report validation failure
12
133. visited = new mapping from each vertex in adjacencyList to false
144. distance = new mapping from each vertex in adjacencyList to -1
155. order = new empty list
166. queue = new empty FIFO queue
17
187. visited[start] = true
198. distance[start] = 0
209. enqueue(queue, start)
2110. append order, start
22
2311. while queue is not empty:
2412. current = dequeue(queue)
25
2613. for each neighbor in adjacencyList[current], in listed order:
2714. if visited[neighbor] is false:
2815. visited[neighbor] = true
2916. distance[neighbor] = distance[current] + 1
3017. enqueue(queue, neighbor)
3118. append order, neighbor
32
3319. return (order, distance)bfsOrder and bfsDistances use the same traversal helper.
1function bfsOrder(adjacencyList, start):
2 input:
3 adjacencyList: mapping Vertex -> ordered list of Vertex
4 start: Vertex
5 returns:
6 list of vertices in BFS discovery order
7 mutation:
8 does not modify adjacencyList
9
101. (order, distance) = runBFS(adjacencyList, start)
112. return order1function bfsDistances(adjacencyList, start):
2 input:
3 adjacencyList: mapping Vertex -> ordered list of Vertex
4 start: Vertex
5 returns:
6 mapping Vertex -> integer distance
7 unreachable vertices map to -1
8 mutation:
9 does not modify adjacencyList
10
111. (order, distance) = runBFS(adjacencyList, start)
122. return distanceUse the original graph:
1A: [B, C]
2B: [A, D]
3C: [A, D]
4D: [B, C]
5start = ALines 1–2: A is a key, so validation succeeds.
Lines 3–6 create the state:
1visited = {A:false, B:false, C:false, D:false}
2distance = {A:-1, B:-1, C:-1, D:-1}
3order = []
4queue = []Lines 7–10 initialize the start vertex:
1visited[A] = true
2distance[A] = 0
3queue = [A]
4order = [A]Line 11: the queue is not empty.
Line 12:
1current = dequeue(queue) = A
2queue = []Line 13 inspects A’s neighbors in order: B, then C.
For B, line 14 finds visited[B] = false.
Lines 15–18:
1visited[B] = true
2distance[B] = distance[A] + 1 = 1
3queue = [B]
4order = [A, B]For C, line 14 finds visited[C] = false.
Lines 15–18:
1visited[C] = true
2distance[C] = distance[A] + 1 = 1
3queue = [B, C]
4order = [A, B, C]Line 12 removes B:
1current = B
2queue = [C]Line 13 inspects B’s neighbors: A, then D.
For A, line 14 finds visited[A] = true, so no state changes.
For D, line 14 finds visited[D] = false.
Lines 15–18:
1visited[D] = true
2distance[D] = distance[B] + 1 = 2
3queue = [C, D]
4order = [A, B, C, D]Line 12 removes C:
1current = C
2queue = [D]Line 13 inspects A, then D.
Both are already visited, so lines 15–18 do not run.
1queue = [D]
2order = [A, B, C, D]Line 12 removes D:
1current = D
2queue = []Line 13 inspects B, then C.
Both are already visited. No vertex is added.
Line 11 now finds an empty queue.
Line 19 returns:
1order = [A, B, C, D]
2
3distance = {
4 A: 0,
5 B: 1,
6 C: 1,
7 D: 2
8}We show that runBFS returns each reachable vertex once, gives it the correct shortest edge-count distance, and leaves unreachable vertices at -1.
Before the loop:
0 on line 8.Every queued vertex is visited and has a known distance. At this moment, the queue contains only the start, so queue distances are in nondecreasing order.
The invariant holds before the first iteration.
Assume the invariant holds when an iteration begins.
The algorithm dequeues current. By the invariant, current is visited and has a known shortest distance.
For every neighbor:
distance[current] + 1, and enqueue it.The new neighbor is exactly one edge away from current, so the assigned distance describes a path from the start.
Vertices are dequeued in nondecreasing distance order. Before processing current, all vertices at smaller distances have already had their adjacency lists inspected. If the new neighbor had a shorter route, a predecessor on that shorter route would have been processed earlier and would already have discovered the neighbor. The neighbor is unvisited, so no shorter route exists.
The neighbor is appended to the rear of the FIFO queue. Its distance is one greater than current’s distance, so it cannot be placed ahead of a vertex with a larger distance. Queue distances remain in nondecreasing order.
The invariant is preserved.
Each vertex is marked visited before it is enqueued. No vertex enters the queue more than once. The graph has finitely many vertices, so eventually the queue becomes empty.
When the queue is empty, every discovered vertex has been dequeued and its neighbors have been inspected. Any vertex reachable from the start must be reached by following neighbors from already discovered vertices, so it must have been discovered. Conversely, a vertex never discovered has no explored path from the start and remains unvisited with distance -1.
The algorithm returns BFS discovery order and correct shortest edge-count distances for reachable vertices.
Let:
V be the number of vertices in the graph.E be the number of edges.First count vertex work.
A reachable vertex is marked visited before enqueueing. That means it is:
Next count neighbor-inspection work.
When a vertex is dequeued, line 13 scans its adjacency list once. Across all adjacency lists, each adjacency entry is inspected once. In an undirected graph, every edge appears in two adjacency lists, for 2E entries. That is still O(E).
Initialization in lines 3 and 4 can touch all V vertices.
So the total time is:
1O(V) initialization + O(V) queue operations + O(E) adjacency inspections
2= O(V + E)The visited mapping can hold V entries. The distance mapping can hold V entries. The queue can also hold up to V vertices.
So auxiliary space is:
1O(V)The graph representation itself is excluded.
Incorrect assumption:
1worklist removes the most recently added vertexExposing input:
1A: [B, C]
2B: [D]
3C: []
4D: []Starting from A, a stack can produce:
1[A, C, B, D]That is depth-first-style behavior. BFS discovery order must be:
1[A, B, C, D]Correction: remove vertices from the front of a FIFO queue.
Incorrect line placement:
1enqueue(queue, neighbor)
2visited[neighbor] = trueOr delay the mark until the vertex is later dequeued.
Exposing input:
1A: [B, C]
2B: [D]
3C: [D]
4D: []After processing B, D is enqueued. If D is not marked yet, processing C sees D as unvisited and enqueues it again.
Wrong queue state:
1[D, D]Correction: mark D visited before its first enqueue.
1visited[D] = true
2enqueue(queue, D)Incorrect assumption:
1after scanning start, traversal is completeExposing input:
1A: [B]
2B: [A, C]
3C: [B]Stopping after processing A returns:
1[A, B]C is reachable through B.
Correct result:
1[A, B, C]Correction: continue the loop until the queue is empty.
Incorrect line:
1distance[neighbor] = 1Exposing input:
1A: [B]
2B: [A, C]
3C: [B]The wrong result is:
1distance(C) = 1Reaching C from A requires two edges:
1A -> B -> CCorrection:
1distance[neighbor] = distance[current] + 1| Input | Start | Expected result |
|---|---|---|
A: [] | A | Order [A]; the queue empties after dequeuing A. |
A: [B], B: [A], C: [] | A | Order [A, B]; C remains unvisited and has distance -1. |
A: [B, C], B: [A, C], C: [A, B] | A | Each vertex appears once, even though the cycle gives multiple routes. |
A: [B, B], B: [] | A | B is enqueued once because it is marked visited at first discovery. |
A: [] | Z | Validation failure because Z is not a graph vertex. |
Implement these functions:
1bfsOrder(adjacencyList, start)It returns vertices in discovery order.
1bfsDistances(adjacencyList, start)It returns each reachable vertex’s BFS distance and returns -1 for unreachable vertices.
The contract to test is:
distance(neighbor) = distance(current) + 1,Tests cover cycles, duplicate adjacency entries, and disconnected graphs.
1from collections import deque
2
3def run_bfs(adj, start):
4 if start not in adj:
5 raise ValueError("start must be a vertex")
6 visited = {v: False for v in adj}
7 distance = {v: -1 for v in adj}
8 order = []
9 queue = deque()
10
11 visited[start] = True
12 distance[start] = 0
13 queue.append(start)
14 order.append(start)
15
16 while queue:
17 current = queue.popleft()
18 for neighbor in adj[current]: # listed order
19 if not visited[neighbor]:
20 visited[neighbor] = True # mark before enqueueing
21 distance[neighbor] = distance[current] + 1
22 queue.append(neighbor)
23 order.append(neighbor)
24 return order, distance
25
26adj = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
27order, distance = run_bfs(adj, "A")
28print("order:", " ".join(order))
29print("distance:", " ".join(f"{v}={d}" for v, d in distance.items()))1import java.util.*;
2
3public class Main {
4 static List<String> order = new ArrayList<>();
5 static Map<String, Integer> distance = new LinkedHashMap<>();
6
7 static void runBfs(Map<String, List<String>> adj, String start) {
8 if (!adj.containsKey(start)) throw new IllegalArgumentException("start must be a vertex");
9 Map<String, Boolean> visited = new HashMap<>();
10 for (String v : adj.keySet()) {
11 visited.put(v, false);
12 distance.put(v, -1);
13 }
14 Deque<String> queue = new ArrayDeque<>();
15
16 visited.put(start, true);
17 distance.put(start, 0);
18 queue.addLast(start);
19 order.add(start);
20
21 while (!queue.isEmpty()) {
22 String current = queue.pollFirst();
23 for (String neighbor : adj.get(current)) { // listed order
24 if (!visited.get(neighbor)) {
25 visited.put(neighbor, true); // mark before enqueueing
26 distance.put(neighbor, distance.get(current) + 1);
27 queue.addLast(neighbor);
28 order.add(neighbor);
29 }
30 }
31 }
32 }
33
34 public static void main(String[] args) {
35 Map<String, List<String>> adj = new LinkedHashMap<>();
36 adj.put("A", List.of("B", "C"));
37 adj.put("B", List.of("A", "D"));
38 adj.put("C", List.of("A", "D"));
39 adj.put("D", List.of("B", "C"));
40 runBfs(adj, "A");
41 System.out.println("order: " + String.join(" ", order));
42 StringBuilder sb = new StringBuilder();
43 for (Map.Entry<String, Integer> e : distance.entrySet()) {
44 sb.append(sb.length() > 0 ? " " : "").append(e.getKey()).append("=").append(e.getValue());
45 }
46 System.out.println("distance: " + sb);
47 }
48}1#include <iostream>
2#include <map>
3#include <queue>
4#include <string>
5#include <vector>
6using namespace std;
7
8int main() {
9 map<string, vector<string>> adj = {
10 {"A", {"B", "C"}}, {"B", {"A", "D"}}, {"C", {"A", "D"}}, {"D", {"B", "C"}}};
11 string start = "A";
12 if (!adj.count(start)) return 1;
13
14 map<string, bool> visited;
15 map<string, int> distance;
16 for (const auto& kv : adj) {
17 visited[kv.first] = false;
18 distance[kv.first] = -1;
19 }
20 vector<string> order;
21 queue<string> q;
22
23 visited[start] = true;
24 distance[start] = 0;
25 q.push(start);
26 order.push_back(start);
27
28 while (!q.empty()) {
29 string current = q.front();
30 q.pop();
31 for (const string& neighbor : adj[current]) { // listed order
32 if (!visited[neighbor]) {
33 visited[neighbor] = true; // mark before enqueueing
34 distance[neighbor] = distance[current] + 1;
35 q.push(neighbor);
36 order.push_back(neighbor);
37 }
38 }
39 }
40
41 cout << "order:";
42 for (const string& v : order) cout << " " << v;
43 cout << "\ndistance:";
44 for (const auto& kv : distance) cout << " " << kv.first << "=" << kv.second;
45 cout << endl;
46}1function runBfs(adj, start) {
2 if (!adj.has(start)) throw new Error('start must be a vertex');
3 const visited = new Map();
4 const distance = new Map();
5 for (const v of adj.keys()) {
6 visited.set(v, false);
7 distance.set(v, -1);
8 }
9 const order = [];
10 const queue = [];
11
12 visited.set(start, true);
13 distance.set(start, 0);
14 queue.push(start);
15 order.push(start);
16
17 let head = 0; // index of the queue front
18 while (head < queue.length) {
19 const current = queue[head++];
20 for (const neighbor of adj.get(current)) { // listed order
21 if (!visited.get(neighbor)) {
22 visited.set(neighbor, true); // mark before enqueueing
23 distance.set(neighbor, distance.get(current) + 1);
24 queue.push(neighbor);
25 order.push(neighbor);
26 }
27 }
28 }
29 return { order, distance };
30}
31
32const adj = new Map([
33 ['A', ['B', 'C']],
34 ['B', ['A', 'D']],
35 ['C', ['A', 'D']],
36 ['D', ['B', 'C']],
37]);
38const { order, distance } = runBfs(adj, 'A');
39console.log(`order: ${order.join(' ')}`);
40console.log(`distance: ${[...distance].map(([v, d]) => `${v}=${d}`).join(' ')}`);BFS uses a FIFO queue and goes layer by layer. DFS follows one path as far as it can, then backs up. On the example graph from A, BFS gives A, B, C, D and DFS gives A, B, D, C.
Marking at discovery stops a second vertex from enqueueing the same one. With A: [B, C], B: [D], C: [D], marking only on dequeue puts D in the queue twice.
Vertices leave the queue in nondecreasing distance, and each new vertex gets distance[current] + 1. A shorter route would already have been found by an earlier vertex. This counts edges, not weights.
O(V + E) with adjacency lists. Each vertex is enqueued and dequeued at most once, and each adjacency entry is scanned once, which is 2E entries in an undirected graph.
It leaves them unvisited with distance -1. BFS covers only what the start can reach, so a disconnected graph needs one run per component.