33.01Intermediate / Advanced5 topics16 min5 interactive animations

Breadth-first search

Breadth-first search explores a graph layer by layer with a queue: every vertex at distance d is visited before any at distance d + 1, which makes it the tool for fewest-edge paths.

Learning goals

Run BFS with a queue and explain why it visits vertices in order of distance
Mark vertices when they are enqueued so each enters the queue once
Compute unweighted shortest distances and rebuild a path from parent links
Start the search from several sources at once

Prerequisites

Graph representationsQueues

Asked for the fewest hops between two people in a social network, or the fewest moves in a puzzle, you want to try everything one step away, then everything two steps away, and so on. A queue gives exactly that order.

33.01.1

Queue frontier

BFS keeps a **frontier**: the vertices discovered but not yet expanded. It lives in a FIFO queue. Take the vertex at the front, look at each neighbour, and add the ones not seen before to the back. Because new vertices go to the back, every vertex at distance d leaves the queue before any vertex at distance d + 1.

In the animation choose *BFS distances, undirected* and step through: the queue strip shows the frontier, and the layers appear as distance labels on the vertices. Each vertex is enqueued once and each adjacency entry is looked at once, so the work is proportional to n + m with an adjacency list.

Java

1static List<Integer> bfsOrder(List<List<Integer>> g, int s) {   // vertices in the order BFS expands them
2    boolean[] seen = new boolean[g.size()];
3    List<Integer> order = new ArrayList<>();
4    Deque<Integer> queue = new ArrayDeque<>();
5    seen[s] = true;
6    queue.add(s);
7    while (!queue.isEmpty()) {
8        int u = queue.poll();                    // front of the queue: the oldest discovered vertex
9        order.add(u);
10        for (int v : g.get(u))
11            if (!seen[v]) { seen[v] = true; queue.add(v); }
12    }
13    return order;
14}

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).

33.01.2

Visited array

The seen array is what stops BFS from looping on a cycle and from queueing a vertex many times. The important detail is *when* to mark: mark a vertex the moment it is **added** to the queue, not when it is removed. If you wait until removal, a vertex with several neighbours in the frontier is queued once per neighbour and the queue can grow to m entries instead of n.

Marking on enqueue also fixes the distance at the right moment: the first time a vertex is discovered is through a shortest path, so that distance never needs to be revised.

Java

1static int enqueueCount(List<List<Integer>> g, int s, boolean markOnEnqueue) {   // how many times vertices enter the queue
2    boolean[] seen = new boolean[g.size()];
3    Deque<Integer> queue = new ArrayDeque<>();
4    int pushes = 1;
5    queue.add(s);
6    if (markOnEnqueue) seen[s] = true;
7    while (!queue.isEmpty()) {
8        int u = queue.poll();
9        if (!markOnEnqueue) { if (seen[u]) continue; seen[u] = true; }   // late marking: duplicates must be skipped here
10        for (int v : g.get(u))
11            if (!seen[v]) {
12                if (markOnEnqueue) seen[v] = true;
13                queue.add(v);
14                pushes++;
15            }
16    }
17    return pushes;
18}

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).

33.01.3

Unweighted shortest distance

Store a distance with each vertex: the source has 0, and a vertex discovered from u gets dist[u] + 1. Because BFS expands vertices in order of distance, the first discovery of a vertex is along a path with the fewest edges, so dist[v] is the length of a shortest path from the source. A vertex that is never reached keeps -1.

This only counts edges. With weights a path of fewer edges can cost more, so weighted shortest paths need Dijkstra or a variant, covered in the shortest-path chapters. Try the *directed* option in the animation to see unreachable vertices keep their -1.

Java

1static int[] bfsDist(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); }   // dist doubles as the visited array
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).

33.01.4

BFS parent tree

Record parent[v] = u when v is first discovered from u. The parent links form a tree rooted at the source, the **BFS tree**, and the tree path from the source to any vertex is a shortest path. To print a path, follow parents from the target back to the source and reverse the list.

Choose *Shortest path to a destination* in the animation: the final frames highlight the tree path. If the target was never discovered, there is no path and the answer is empty.

Java

1static List<Integer> bfsPath(List<List<Integer>> g, int s, int t) {   // a fewest-edge path from s to t, or empty
2    int[] parent = new int[g.size()];
3    Arrays.fill(parent, -2);                     // -2 = undiscovered, -1 = the source
4    Deque<Integer> queue = new ArrayDeque<>();
5    parent[s] = -1;
6    queue.add(s);
7    while (!queue.isEmpty() && parent[t] == -2) {
8        int u = queue.poll();
9        for (int v : g.get(u))
10            if (parent[v] == -2) { parent[v] = u; queue.add(v); }
11    }
12    LinkedList<Integer> path = new LinkedList<>();
13    if (parent[t] == -2) return path;
14    for (int v = t; v != -1; v = parent[v]) path.addFirst(v);
15    return path;
16}

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).

33.01.5

Multi-source BFS

Put **every** source in the queue at distance 0 before the loop starts. The search then grows from all of them at the same speed, and each vertex receives the distance to its *nearest* source. This is the same as adding an imaginary vertex joined to all sources and running a normal BFS from it.

It answers questions such as the distance from each cell to the nearest fire, hospital or 0 cell in a single O(n + m) pass, instead of one search per source. Use the *Multi-source* option in the animation and list two sources.

Java

1static int[] multiSourceDist(List<List<Integer>> g, int[] sources) {   // distance to the nearest source
2    int[] dist = new int[g.size()];
3    Arrays.fill(dist, -1);
4    Deque<Integer> queue = new ArrayDeque<>();
5    for (int s : sources)
6        if (dist[s] == -1) { dist[s] = 0; queue.add(s); }                // all sources start the search together
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).

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Shortest Path in Binary Matrix
01 Matrix
Rotting Oranges

Advanced

Shortest Path Visiting All Nodes
As Far from Land as Possible

Key takeaways

BFS expands vertices in order of distance, using a queue; the work is O(n + m) on an adjacency list.
Mark a vertex when it is enqueued so it is queued at most once.
The first discovery gives the fewest-edge distance; parent links give the path.
Start with all sources in the queue to get the distance to the nearest source in one pass.