35.02Intermediate / Advanced4 topics13 min4 interactive animations

Unweighted and binary weights

When every edge costs 1, BFS is the shortest-path algorithm; with edges of weight 0 or 1 a deque does the same job, and the distance layers explain why both are linear.

Learning goals

Use BFS for fewest-edge paths and for the nearest of several sources
Solve 0-1 weighted shortest paths with a deque
Describe the distance layers of a BFS

Prerequisites

Breadth-first searchShortest path framework

Many graph problems have no real weights: the fewest moves, the fewest flips. Others have free moves and costly moves. These special cases are simpler and faster than general Dijkstra, and recognising them saves a log factor.

35.02.1

BFS

With every edge of weight 1 the cost of a path is its number of edges, and BFS visits vertices in order of distance. The first time BFS reaches a vertex is along a shortest path, so no relaxation needs repeating: each vertex is set once, in O(n + m).

BFS is exactly Dijkstra with a plain queue in place of a priority queue; the queue stays sorted because every new distance is one more than the last. The BFS animation shows the queue and the distances.

Java

1static int[] hopDistances(List<List<Integer>> g, int s) {        // fewest edges from s; -1 when unreachable
2    int[] dist = new int[g.size()];
3    Arrays.fill(dist, -1);
4    Deque<Integer> queue = new ArrayDeque<>();
5    dist[s] = 0;
6    queue.add(s);
7    while (!queue.isEmpty()) {
8        int u = queue.poll();
9        for (int v : g.get(u))
10            if (dist[v] == -1) { dist[v] = dist[u] + 1; queue.add(v); }
11    }
12    return dist;
13}

Breadth-first search: queue, distances, parent tree, multiple sources

Interactive · edit the input

undirected graph · 7 vertices · 8 edges

d=0

Being expandedIn the queueFinishedTree edge / on the path

queue (front first)

dist[v]

-1

-2

-3

-4

-5

-6

parent[v]

-0

-1

-2

-3

-4

-5

-6

Setup

Start at 0: it gets distance 0 and goes into the queue. A vertex is marked when it is enqueued, not when it is dequeued, so it can never be queued twice.

Step 1 / 25

Java

1int[] bfs(List<List<Integer>> g, int s) {
2    int n = g.size(); int[] dist = new int[n];
3    Arrays.fill(dist, -1);                       // -1: not discovered yet
4    Deque<Integer> q = new ArrayDeque<>();
5    dist[s] = 0; q.add(s);                       // the source is discovered when it is enqueued
6    while (!q.isEmpty()) {
7        int u = q.poll();
8        for (int v : g.get(u)) {
9            if (dist[v] != -1) continue;         // already discovered: never enqueue twice
10            dist[v] = dist[u] + 1;               // parent[v] = u would record the tree edge
11            q.add(v);
12        }
13    }
14    return dist;
15}
16int[] bfsMulti(List<List<Integer>> g, int[] sources) {   // distance to the nearest source
17    int[] dist = new int[g.size()]; Arrays.fill(dist, -1);
18    Deque<Integer> q = new ArrayDeque<>();
19    for (int s : sources) { dist[s] = 0; q.add(s); }      // every source starts at distance 0
20    while (!q.isEmpty()) { int u = q.poll(); for (int v : g.get(u)) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); } }
21    return dist;
22}
23List<Integer> path(int[] parent, int t) {        // read the path off the BFS parent tree
24    LinkedList<Integer> p = new LinkedList<>();
25    for (int v = t; v != -1; v = parent[v]) p.addFirst(v);
26    return p;
27}

Live state

1 vertices enqueued0 edges examined

source

queue

[0]

No condition evaluated on this step

Execution trace (dry run table)Show 25 steps

Step	Line	State	What happens
1	L5	source=0 queue=[0]	Start at 0: it gets distance 0 and goes into the queue. A vertex is marked when it is enqueued, not when it is dequeued, so it can never be queued twice.
2	L7	u=0 dist[u]=0 queue=[]	Dequeue 0 (distance 0): look at all of its neighbours.
3	L10	u=0 v=1 dist[v]=1 queue=[1]	0 - 1: 1 is new. dist[1] = dist[0] + 1 = 1, parent[1] = 0, and 1 joins the back of the queue. The edge becomes a tree edge.
4	L10	u=0 v=2 dist[v]=1 queue=[1, 2]	0 - 2: 2 is new. dist[2] = dist[0] + 1 = 1, parent[2] = 0, and 2 joins the back of the queue. The edge becomes a tree edge.
5	L7	u=1 dist[u]=1 queue=[2]	Dequeue 1 (distance 1): look at all of its neighbours.
6	L9	u=1 v=0 dist[v]=0	1 - 0: 0 already has distance 0, so it was discovered earlier by a path that is no longer: skip.
7	L10	u=1 v=3 dist[v]=2 queue=[2, 3]	1 - 3: 3 is new. dist[3] = dist[1] + 1 = 2, parent[3] = 1, and 3 joins the back of the queue. The edge becomes a tree edge.
8	L7	u=2 dist[u]=1 queue=[3]	Dequeue 2 (distance 1): look at all of its neighbours.
9	L9	u=2 v=0 dist[v]=0	2 - 0: 0 already has distance 0, so it was discovered earlier by a path that is no longer: skip.
10	L9	u=2 v=3 dist[v]=2	2 - 3: 3 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
11	L10	u=2 v=4 dist[v]=2 queue=[3, 4]	2 - 4: 4 is new. dist[4] = dist[2] + 1 = 2, parent[4] = 2, and 4 joins the back of the queue. The edge becomes a tree edge.
12	L7	u=3 dist[u]=2 queue=[4]	Dequeue 3 (distance 2): look at all of its neighbours.
13	L9	u=3 v=1 dist[v]=1	3 - 1: 1 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
14	L9	u=3 v=2 dist[v]=1	3 - 2: 2 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
15	L10	u=3 v=5 dist[v]=3 queue=[4, 5]	3 - 5: 5 is new. dist[5] = dist[3] + 1 = 3, parent[5] = 3, and 5 joins the back of the queue. The edge becomes a tree edge.
16	L7	u=4 dist[u]=2 queue=[5]	Dequeue 4 (distance 2): look at all of its neighbours.
17	L9	u=4 v=2 dist[v]=1	4 - 2: 2 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
18	L9	u=4 v=5 dist[v]=3	4 - 5: 5 already has distance 3, so it was discovered earlier by a path that is no longer: skip.
19	L7	u=5 dist[u]=3 queue=[]	Dequeue 5 (distance 3): look at all of its neighbours.
20	L9	u=5 v=3 dist[v]=2	5 - 3: 3 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
21	L9	u=5 v=4 dist[v]=2	5 - 4: 4 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
22	L10	u=5 v=6 dist[v]=4 queue=[6]	5 - 6: 6 is new. dist[6] = dist[5] + 1 = 4, parent[6] = 5, and 6 joins the back of the queue. The edge becomes a tree edge.
23	L7	u=6 dist[u]=4 queue=[]	Dequeue 6 (distance 4): look at all of its neighbours.
24	L9	u=6 v=5 dist[v]=3	6 - 5: 5 already has distance 3, so it was discovered earlier by a path that is no longer: skip.
25	L14	return=[0, 1, 1, 2, 2, 3, 4] vertices enqueued=7 edges examined=16	Distances: [0, 1, 1, 2, 2, 3, 4] ('-' = unreachable). Each vertex was enqueued once and each edge examined from both ends: 16 examinations, O(V + E).

35.02.2

Multi-source BFS

Start the queue with every source at distance 0 to get, for each vertex, the distance to the nearest source in one pass. This is the same as one search from an imaginary vertex that has a free edge to each source.

Use it for "distance to the nearest 0 in a matrix", "how long until all oranges rot", or the distance to the nearest facility. Choose the *Multi-source* option in the animation.

Java

1static int[] nearestSourceHops(List<List<Integer>> g, int[] sources) {
2    int[] dist = new int[g.size()];
3    Arrays.fill(dist, -1);
4    Deque<Integer> queue = new ArrayDeque<>();
5    for (int s : sources) if (dist[s] == -1) { dist[s] = 0; queue.add(s); }   // all sources start together
6    while (!queue.isEmpty()) {
7        int u = queue.poll();
8        for (int v : g.get(u))
9            if (dist[v] == -1) { dist[v] = dist[u] + 1; queue.add(v); }
10    }
11    return dist;
12}

Breadth-first search: queue, distances, parent tree, multiple sources

Interactive · edit the input

undirected graph · 7 vertices · 8 edges

d=0

Being expandedIn the queueFinishedTree edge / on the path

queue (front first)

dist[v]

-1

-2

-3

-4

-5

-6

parent[v]

-0

-1

-2

-3

-4

-5

-6

Setup

Start at 0: it gets distance 0 and goes into the queue. A vertex is marked when it is enqueued, not when it is dequeued, so it can never be queued twice.

Step 1 / 25

Java

1int[] bfs(List<List<Integer>> g, int s) {
2    int n = g.size(); int[] dist = new int[n];
3    Arrays.fill(dist, -1);                       // -1: not discovered yet
4    Deque<Integer> q = new ArrayDeque<>();
5    dist[s] = 0; q.add(s);                       // the source is discovered when it is enqueued
6    while (!q.isEmpty()) {
7        int u = q.poll();
8        for (int v : g.get(u)) {
9            if (dist[v] != -1) continue;         // already discovered: never enqueue twice
10            dist[v] = dist[u] + 1;               // parent[v] = u would record the tree edge
11            q.add(v);
12        }
13    }
14    return dist;
15}
16int[] bfsMulti(List<List<Integer>> g, int[] sources) {   // distance to the nearest source
17    int[] dist = new int[g.size()]; Arrays.fill(dist, -1);
18    Deque<Integer> q = new ArrayDeque<>();
19    for (int s : sources) { dist[s] = 0; q.add(s); }      // every source starts at distance 0
20    while (!q.isEmpty()) { int u = q.poll(); for (int v : g.get(u)) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); } }
21    return dist;
22}
23List<Integer> path(int[] parent, int t) {        // read the path off the BFS parent tree
24    LinkedList<Integer> p = new LinkedList<>();
25    for (int v = t; v != -1; v = parent[v]) p.addFirst(v);
26    return p;
27}

Live state

1 vertices enqueued0 edges examined

source

queue

[0]

No condition evaluated on this step

Execution trace (dry run table)Show 25 steps

Step	Line	State	What happens
1	L5	source=0 queue=[0]	Start at 0: it gets distance 0 and goes into the queue. A vertex is marked when it is enqueued, not when it is dequeued, so it can never be queued twice.
2	L7	u=0 dist[u]=0 queue=[]	Dequeue 0 (distance 0): look at all of its neighbours.
3	L10	u=0 v=1 dist[v]=1 queue=[1]	0 - 1: 1 is new. dist[1] = dist[0] + 1 = 1, parent[1] = 0, and 1 joins the back of the queue. The edge becomes a tree edge.
4	L10	u=0 v=2 dist[v]=1 queue=[1, 2]	0 - 2: 2 is new. dist[2] = dist[0] + 1 = 1, parent[2] = 0, and 2 joins the back of the queue. The edge becomes a tree edge.
5	L7	u=1 dist[u]=1 queue=[2]	Dequeue 1 (distance 1): look at all of its neighbours.
6	L9	u=1 v=0 dist[v]=0	1 - 0: 0 already has distance 0, so it was discovered earlier by a path that is no longer: skip.
7	L10	u=1 v=3 dist[v]=2 queue=[2, 3]	1 - 3: 3 is new. dist[3] = dist[1] + 1 = 2, parent[3] = 1, and 3 joins the back of the queue. The edge becomes a tree edge.
8	L7	u=2 dist[u]=1 queue=[3]	Dequeue 2 (distance 1): look at all of its neighbours.
9	L9	u=2 v=0 dist[v]=0	2 - 0: 0 already has distance 0, so it was discovered earlier by a path that is no longer: skip.
10	L9	u=2 v=3 dist[v]=2	2 - 3: 3 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
11	L10	u=2 v=4 dist[v]=2 queue=[3, 4]	2 - 4: 4 is new. dist[4] = dist[2] + 1 = 2, parent[4] = 2, and 4 joins the back of the queue. The edge becomes a tree edge.
12	L7	u=3 dist[u]=2 queue=[4]	Dequeue 3 (distance 2): look at all of its neighbours.
13	L9	u=3 v=1 dist[v]=1	3 - 1: 1 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
14	L9	u=3 v=2 dist[v]=1	3 - 2: 2 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
15	L10	u=3 v=5 dist[v]=3 queue=[4, 5]	3 - 5: 5 is new. dist[5] = dist[3] + 1 = 3, parent[5] = 3, and 5 joins the back of the queue. The edge becomes a tree edge.
16	L7	u=4 dist[u]=2 queue=[5]	Dequeue 4 (distance 2): look at all of its neighbours.
17	L9	u=4 v=2 dist[v]=1	4 - 2: 2 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
18	L9	u=4 v=5 dist[v]=3	4 - 5: 5 already has distance 3, so it was discovered earlier by a path that is no longer: skip.
19	L7	u=5 dist[u]=3 queue=[]	Dequeue 5 (distance 3): look at all of its neighbours.
20	L9	u=5 v=3 dist[v]=2	5 - 3: 3 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
21	L9	u=5 v=4 dist[v]=2	5 - 4: 4 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
22	L10	u=5 v=6 dist[v]=4 queue=[6]	5 - 6: 6 is new. dist[6] = dist[5] + 1 = 4, parent[6] = 5, and 6 joins the back of the queue. The edge becomes a tree edge.
23	L7	u=6 dist[u]=4 queue=[]	Dequeue 6 (distance 4): look at all of its neighbours.
24	L9	u=6 v=5 dist[v]=3	6 - 5: 5 already has distance 3, so it was discovered earlier by a path that is no longer: skip.
25	L14	return=[0, 1, 1, 2, 2, 3, 4] vertices enqueued=7 edges examined=16	Distances: [0, 1, 1, 2, 2, 3, 4] ('-' = unreachable). Each vertex was enqueued once and each edge examined from both ends: 16 examinations, O(V + E).

35.02.3

0-1 BFS using deque

When edge weights are only 0 or 1, keep a deque in which distances never decrease from front to back. Relaxing a **0-edge** leaves the distance unchanged, so the head goes to the *front*; relaxing a **1-edge** adds one, so the head goes to the *back*. Pop from the front as in BFS.

A vertex can be pushed more than once (a free edge may later improve it), but the deque still gives a total of O(n + m) work, better than Dijkstra's O((n + m) log n). Typical uses are grid problems where moving along a marked cell is free and changing direction costs 1.

Java

1static int[] bfs01(int n, List<int[]>[] adj, int s) {             // adj[u] = {v, 0 or 1}; Integer.MAX_VALUE = unreachable
2    int[] dist = new int[n];
3    Arrays.fill(dist, Integer.MAX_VALUE);
4    dist[s] = 0;
5    Deque<Integer> dq = new ArrayDeque<>();
6    dq.add(s);
7    while (!dq.isEmpty()) {
8        int u = dq.pollFirst();
9        for (int[] e : adj[u]) {
10            if (dist[u] + e[1] >= dist[e[0]]) continue;
11            dist[e[0]] = dist[u] + e[1];
12            if (e[1] == 0) dq.addFirst(e[0]); else dq.addLast(e[0]);   // free move to the front, cost 1 to the back
13        }
14    }
15    return dist;
16}

0-1 BFS: a deque for edges of weight 0 and 1

Interactive · edit the input

undirected graph · 6 vertices · 7 edges

d=0

Being expandedIn the dequeExpandedTree edge

deque (front first)

dist[v]

∞1

∞2

∞3

∞4

∞5

Setup

With weights 0 and 1 the deque holds vertices sorted by distance: a 0-edge keeps the distance, so its head goes to the front; a 1-edge adds one, so its head goes to the back.

Step 1 / 22

Java

1int[] bfs01(int n, List<int[]>[] adj, int s) {    // adj[u] = {v, 0 or 1}
2    int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[s] = 0;
3    Deque<Integer> dq = new ArrayDeque<>(); dq.add(s);
4    while (!dq.isEmpty()) {
5        int u = dq.pollFirst();
6        for (int[] e : adj[u]) {
7            if (dist[u] + e[1] >= dist[e[0]]) continue;
8            dist[e[0]] = dist[u] + e[1];
9            if (e[1] == 0) dq.addFirst(e[0]); else dq.addLast(e[0]);   // free move to the front, cost 1 to the back
10        }
11    }
12    return dist;
13}

Live state

0 vertices expanded0 improvements

source

No condition evaluated on this step

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L3	source=0	With weights 0 and 1 the deque holds vertices sorted by distance: a 0-edge keeps the distance, so its head goes to the front; a 1-edge adds one, so its head goes to the back.
2	L5	u=0 dist[u]=0	Take 0 from the front (distance 0).
3	L9	u=0 v=1 dist[v]=1	0 → 1 (weight 1): dist[1] = 1. A weight-1 edge puts 1 at the back of the deque.
4	L9	u=0 v=2 dist[v]=0	0 → 2 (weight 0): dist[2] = 0. A weight-0 edge puts 2 at the front of the deque.
5	L5	u=2 dist[u]=0	Take 2 from the front (distance 0).
6	L7	u=2 v=0 candidate=0	2 → 0 (weight 0): 0 is not better than 0.
7	L9	u=2 v=3 dist[v]=1	2 → 3 (weight 1): dist[3] = 1. A weight-1 edge puts 3 at the back of the deque.
8	L9	u=2 v=5 dist[v]=1	2 → 5 (weight 1): dist[5] = 1. A weight-1 edge puts 5 at the back of the deque.
9	L5	u=1 dist[u]=1	Take 1 from the front (distance 1).
10	L7	u=1 v=0 candidate=2	1 → 0 (weight 1): 2 is not better than 0.
11	L7	u=1 v=3 candidate=1	1 → 3 (weight 0): 1 is not better than 1.
12	L5	u=3 dist[u]=1	Take 3 from the front (distance 1).
13	L7	u=3 v=2 candidate=2	3 → 2 (weight 1): 2 is not better than 0.
14	L7	u=3 v=1 candidate=1	3 → 1 (weight 0): 1 is not better than 1.
15	L9	u=3 v=4 dist[v]=1	3 → 4 (weight 0): dist[4] = 1. A weight-0 edge puts 4 at the front of the deque.
16	L5	u=4 dist[u]=1	Take 4 from the front (distance 1).
17	L7	u=4 v=3 candidate=1	4 → 3 (weight 0): 1 is not better than 1.
18	L7	u=4 v=5 candidate=2	4 → 5 (weight 1): 2 is not better than 1.
19	L5	u=5 dist[u]=1	Take 5 from the front (distance 1).
20	L7	u=5 v=4 candidate=2	5 → 4 (weight 1): 2 is not better than 1.
21	L7	u=5 v=2 candidate=2	5 → 2 (weight 1): 2 is not better than 0.
22	L12	return=[0, 1, 0, 1, 1, 1] vertices expanded=6	Distances: [0, 1, 0, 1, 1, 1] (∞ = unreachable). Each vertex needs only constant work per edge, so the total is O(n + m), faster than Dijkstra's O((n + m) log n).

35.02.4

Distance layering

The vertices at distance d from the source form **layer** d. BFS builds the layers one after another. In an undirected graph every edge joins vertices in the same layer or in neighbouring layers, never layers that are two or more apart; this is why a shortest path cannot skip a layer.

Layers are useful in their own right: the number of layers is the eccentricity of the source, the size of each is a measure of how fast the graph grows, and bidirectional search (later in this chapter) relies on how small the early layers are.

Java

1static List<List<Integer>> layers(List<List<Integer>> g, int s) {   // layers.get(d) = the vertices at distance d
2    int[] dist = new int[g.size()];
3    Arrays.fill(dist, -1);
4    dist[s] = 0;
5    List<List<Integer>> layers = new ArrayList<>();
6    List<Integer> frontier = new ArrayList<>(List.of(s));
7    while (!frontier.isEmpty()) {
8        layers.add(frontier);
9        List<Integer> next = new ArrayList<>();
10        for (int u : frontier)
11            for (int v : g.get(u)) if (dist[v] == -1) { dist[v] = dist[u] + 1; next.add(v); }
12        frontier = next;
13    }
14    return layers;
15}

Breadth-first search: queue, distances, parent tree, multiple sources

Interactive · edit the input

undirected graph · 7 vertices · 8 edges

d=0

Being expandedIn the queueFinishedTree edge / on the path

queue (front first)

dist[v]

-1

-2

-3

-4

-5

-6

parent[v]

-0

-1

-2

-3

-4

-5

-6

Setup

Start at 0: it gets distance 0 and goes into the queue. A vertex is marked when it is enqueued, not when it is dequeued, so it can never be queued twice.

Step 1 / 25

Java

1int[] bfs(List<List<Integer>> g, int s) {
2    int n = g.size(); int[] dist = new int[n];
3    Arrays.fill(dist, -1);                       // -1: not discovered yet
4    Deque<Integer> q = new ArrayDeque<>();
5    dist[s] = 0; q.add(s);                       // the source is discovered when it is enqueued
6    while (!q.isEmpty()) {
7        int u = q.poll();
8        for (int v : g.get(u)) {
9            if (dist[v] != -1) continue;         // already discovered: never enqueue twice
10            dist[v] = dist[u] + 1;               // parent[v] = u would record the tree edge
11            q.add(v);
12        }
13    }
14    return dist;
15}
16int[] bfsMulti(List<List<Integer>> g, int[] sources) {   // distance to the nearest source
17    int[] dist = new int[g.size()]; Arrays.fill(dist, -1);
18    Deque<Integer> q = new ArrayDeque<>();
19    for (int s : sources) { dist[s] = 0; q.add(s); }      // every source starts at distance 0
20    while (!q.isEmpty()) { int u = q.poll(); for (int v : g.get(u)) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); } }
21    return dist;
22}
23List<Integer> path(int[] parent, int t) {        // read the path off the BFS parent tree
24    LinkedList<Integer> p = new LinkedList<>();
25    for (int v = t; v != -1; v = parent[v]) p.addFirst(v);
26    return p;
27}

Live state

1 vertices enqueued0 edges examined

source

queue

[0]

No condition evaluated on this step

Execution trace (dry run table)Show 25 steps

Step	Line	State	What happens
1	L5	source=0 queue=[0]	Start at 0: it gets distance 0 and goes into the queue. A vertex is marked when it is enqueued, not when it is dequeued, so it can never be queued twice.
2	L7	u=0 dist[u]=0 queue=[]	Dequeue 0 (distance 0): look at all of its neighbours.
3	L10	u=0 v=1 dist[v]=1 queue=[1]	0 - 1: 1 is new. dist[1] = dist[0] + 1 = 1, parent[1] = 0, and 1 joins the back of the queue. The edge becomes a tree edge.
4	L10	u=0 v=2 dist[v]=1 queue=[1, 2]	0 - 2: 2 is new. dist[2] = dist[0] + 1 = 1, parent[2] = 0, and 2 joins the back of the queue. The edge becomes a tree edge.
5	L7	u=1 dist[u]=1 queue=[2]	Dequeue 1 (distance 1): look at all of its neighbours.
6	L9	u=1 v=0 dist[v]=0	1 - 0: 0 already has distance 0, so it was discovered earlier by a path that is no longer: skip.
7	L10	u=1 v=3 dist[v]=2 queue=[2, 3]	1 - 3: 3 is new. dist[3] = dist[1] + 1 = 2, parent[3] = 1, and 3 joins the back of the queue. The edge becomes a tree edge.
8	L7	u=2 dist[u]=1 queue=[3]	Dequeue 2 (distance 1): look at all of its neighbours.
9	L9	u=2 v=0 dist[v]=0	2 - 0: 0 already has distance 0, so it was discovered earlier by a path that is no longer: skip.
10	L9	u=2 v=3 dist[v]=2	2 - 3: 3 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
11	L10	u=2 v=4 dist[v]=2 queue=[3, 4]	2 - 4: 4 is new. dist[4] = dist[2] + 1 = 2, parent[4] = 2, and 4 joins the back of the queue. The edge becomes a tree edge.
12	L7	u=3 dist[u]=2 queue=[4]	Dequeue 3 (distance 2): look at all of its neighbours.
13	L9	u=3 v=1 dist[v]=1	3 - 1: 1 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
14	L9	u=3 v=2 dist[v]=1	3 - 2: 2 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
15	L10	u=3 v=5 dist[v]=3 queue=[4, 5]	3 - 5: 5 is new. dist[5] = dist[3] + 1 = 3, parent[5] = 3, and 5 joins the back of the queue. The edge becomes a tree edge.
16	L7	u=4 dist[u]=2 queue=[5]	Dequeue 4 (distance 2): look at all of its neighbours.
17	L9	u=4 v=2 dist[v]=1	4 - 2: 2 already has distance 1, so it was discovered earlier by a path that is no longer: skip.
18	L9	u=4 v=5 dist[v]=3	4 - 5: 5 already has distance 3, so it was discovered earlier by a path that is no longer: skip.
19	L7	u=5 dist[u]=3 queue=[]	Dequeue 5 (distance 3): look at all of its neighbours.
20	L9	u=5 v=3 dist[v]=2	5 - 3: 3 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
21	L9	u=5 v=4 dist[v]=2	5 - 4: 4 already has distance 2, so it was discovered earlier by a path that is no longer: skip.
22	L10	u=5 v=6 dist[v]=4 queue=[6]	5 - 6: 6 is new. dist[6] = dist[5] + 1 = 4, parent[6] = 5, and 6 joins the back of the queue. The edge becomes a tree edge.
23	L7	u=6 dist[u]=4 queue=[]	Dequeue 6 (distance 4): look at all of its neighbours.
24	L9	u=6 v=5 dist[v]=3	6 - 5: 5 already has distance 3, so it was discovered earlier by a path that is no longer: skip.
25	L14	return=[0, 1, 1, 2, 2, 3, 4] vertices enqueued=7 edges examined=16	Distances: [0, 1, 1, 2, 2, 3, 4] ('-' = unreachable). Each vertex was enqueued once and each edge examined from both ends: 16 examinations, O(V + E).

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

01 Matrix
Rotting Oranges
Minimum Obstacle Removal to Reach Corner
Shortest Path in Binary Matrix

Advanced

Minimum Cost to Make at Least One Valid Path in a Grid
Shortest Path in a Grid with Obstacles Elimination

Key takeaways

With all weights equal to 1, BFS is the shortest-path algorithm: O(n + m).
Several sources go into the queue together to give the distance to the nearest one.
0-1 BFS: weight-0 edges push to the front of a deque, weight-1 edges to the back.
BFS layers: in an undirected graph an edge never skips a layer.