Lecture 6: Breadth-First Search

Outline of this Lecture

• The shortest path problem.

• The breadth-first search algorithm.

• The running time of BFS.

• The correctness proof.

Note: We introduce BFS for undirected graphs, but the same

algorithm will also work for directed graphs.

1
 Shortest Paths

e b c

s a

Example: 3 simple paths from the source s to b:

hs, bi, hs, a, bi, hs, e, d, bi
of length 1, 2, 3 respectively. So the shortest path from s to b is
hs, bi. The shortest paths from s to other vertices are
hs, ai, hs, bi, hs, b, ci, hs, b, di, hs, ei.
There are two shortest paths from s to d.

2
 The Shortest Path Problem

e b c

s a

Distance d[v]: The length of a shortest path from s to v.

For example d[c] = 2. We define d[s] = 0.

The Problem: Given a graph G = (V, E) and a source vertex

s ∈ V , find the distances d[v] and a shortest path from s to each
other vertex in G.

3
 What Does the Breadth-First Search Do

Given a graph G = (V, E), the BFS returns

• the distances d[v] from s to v;

• the predecessors pred[v], which is used to derive a short-

est path from s to every other vertex v.

BFS is actually returning a shortest path tree in which the unique

path from s to node u is a shortest path from s to u in the original
graph.

Remarks: In addition to the two arrays d[v] and pred[v], the

BFS also uses another auxiliary array color[v], which has three
possible values:
• white (W, “undiscovered”),
• gray (G, “discovered” but not “processed”),
• black (B, “discovered” and “processed”).

4
 The Breath-First Search

The Idea of the BFS:

Visit the vertices as follows:

1. visit all vertices at distance 1
2. visit all vertices at distance 2
3. visit all vertices at distance 3
etc.

Initially, s is made gray.

When a gray vertex is visited, its color is changed to black,

and the color of all white neighbors is changed to gray.

Gray vertices are kept in a queue Q.

5
 The Breath-First Search

More details.

G given by its adjacency list.

Initialization, first part:

For each vertex u ∈ V ,
color[u] = W ; d[u] = ∞; pred[u] = N IL;

Initialization, second part:

color[s] = G, d[s] = 0, Q = hsi.

Main loop:
if Q is nonempty,
u = dequeue(Q)
for each v ∈ adj[u],
if (color[v] == W ), do
color[v] = G
d[v] = d[u] + 1
pred[v] = u
put v in Q
color[u] = B.

6
 Example of the Breadth-First Search

Problem: Given the following undirected graph and source ver-

tex, find the distance from s to each vertex u ∈ V and the prede-
cessor pred[u] along a shortest path by following the algorithm
described earlier.
b c

a
s f

e d

7
 Example – Continued

Initialization, first part

vertex u s a b c d e f
color[u] W W W W W W W
d[u] ∞ ∞ ∞ ∞ ∞ ∞ ∞
pred[u] NIL NIL NIL NIL NIL NIL NIL

b c

a
s f

e d

8
 Example – Continued

Initialization, second part

vertex u s a b c d e f
color[u] G W W W W W W
d[u] 0 ∞ ∞ ∞ ∞ ∞ ∞
pred[u] NIL NIL NIL NIL NIL NIL NIL

Q = hsi
(Put s into Q (discovered) & mark “G”, meaning “unprocessed”)

b c

a
s 0 f

e d

9
 Example – Continued

While loop, first iteration

Dequeue s from Q. Find adj[s] = hb, ei.

Mark b and e “G”, mark s “B”.
Update d[b], d[e], pred[b], pred[e].
Put b, e in Q.

vertex u s a b c d e f
color[u] B W G W W G W
d[u] 0 ∞ 1 ∞ ∞ 1 ∞
pred[u] NIL NIL s NIL NIL s NIL

Q = hb, ei

b 1 c

a
s 0 f

e d
1

10
 Example – Continued

While loop, second iteration

Dequeue b from Q. Find adj[b] = hs, a, c, f i.

Mark a, c, f “G”, mark b “B”.
Update d[a], d[c], d[f ], pred[a], pred[d], pred[f ].
Put a, c, f in Q.

vertex u s a b c d e f
color[u] B G B G W G G
d[u] 0 2 1 2 ∞ 1 2
pred[u] NIL b s b NIL s b

Q = he, a, c, f i

b 1 2 c

a 2
2 s 0 f

e d
1

11
 Example – Continued

While loop, third iteration

Dequeue e from Q. Find adj[e] = hs, a, d, f i.

Mark d “gray”, mark e “B”.
Update d[d], pred[d].
Put d in Q.

vertex u s a b c d e f
color[u] B G B G G B G
d[u] 0 2 1 2 2 1 2
pred[u] NIL b s b e s b

Q = ha, c, f, di

b 1 2 c

a 2
2 s 0 f

2
e d
1

12
 Example – Continued

While loop, forth iteration

Dequeue a from Q. Find adj[a] = hb, ei.

Mark a “B”.

vertex u s a b c d e f
color[u] B B B G G B G
d[u] 0 2 1 2 2 1 2
pred[u] NIL b s b e s b

Q = hc, f, di

b 1 2 c

a 2
2 s 0 f

2
e d
1

13
 Example – Continued

While loop, fifth iteration

Dequeue c from Q. Find adj[c] = hb, di.

Mark c “B”.

vertex u s a b c d e f
color[u] B B B B G B G
d[u] 0 2 1 2 2 1 2
pred[u] NIL b s b e s b

Q = hf, di

b 1 2 c

a 2
2 s 0 f

2
e d
1

14
 Example – Continued

While loop, sixth iteration

Dequeue f from Q. Find adj[f ] = hb, ei.

Mark f “B”.

vertex u s a b c d e f
color[u] B B B B G B B
d[u] 0 2 1 2 2 1 2
pred[u] NIL b s b e s b

Q = hdi

b 1 2 c

a 2
2 s 0 f

2
e d
1

15
 Example – Continued

While loop, seventh iteration

Dequeue d from Q. Find adj[d] = hc, ei.

Mark d “B”.

vertex u s a b c d e f
color[u] B B B B B B B
d[u] 0 2 1 2 2 1 2
pred[u] NIL b s b e s b

Q=∅

b 1 2 c

a 2
2 s 0 f

2
e d
1

16
 Example – Continued

While loop, eigth iteration

Since Q is empty, stop.

vertex u s a b c d e f
color[u] B B B B B B B
d[u] 0 2 1 2 2 1 2
pred[u] NIL b s b e s b

Q=∅

b 1 2 c

a 2
2 s 0 f

2
e d
1

17
 Example – Continued

b 1 2 c

a 2
2 s 0 f

2
e d
1
Question: How do you construct a shortest path from s to any
vertex by using the following table?

vertex u s a b c d e f
color[u] B B B B B B B
d[u] 0 2 1 2 2 1 2
pred[u] NIL b s b e s b

18
The Breadth-First Search Algorithm

for (each vertex u ∈ V )

{ color[u] = W ;
d[u] = ∞;
pred[u] = N IL;
}
color[s] = G; d[s] = 0; enqueue(Q, s);
if (Q is nonempty)
{ u = dequeue(Q);
for (each v ∈ adj[u])
if (color[v] == W )
{ color[v] = G;
d[v] = d[u] + 1;
pred[v] = u;
enqueue(C, v);
}
color[u] = B;
}

19
 Analysis of the Breadth-First Search Algorithm

Let n = |V | and e = |E|. We assume that it takes one time unit

to test the color of a vertex, or to update the color of a vertex,
or to compute d[v] = d[u] + 1, or to set pred[v] = u, or to
enqueue, or to dequeue.
The following analysis is valid for connected graphs.

• The initialization requires 3n + 3 time units.

• Each vertex u must be processed and is processed once.

What is the total amount of time for processing u?
For each v ∈ adj[u], if color[v] = W , the inner loop takes
4 time units. Otherwise the inner loop will not be carried
out.
dequeue[u] and set color[u] = B take 2 time units. Hence
the total amount of time needed for processing u is at most
5 deg(u) + 2

Hence the total amount of time needed for processing all

the vertices is at most
X
(5 deg(u) + 2) = 10e + 2n.
u∈V

• Hence
T (n, e) ≤ (3n + 3) + (10e + 2n)
= 5n + 10e + 3 = O(n + e).

20
 Analysis of the Breadth-First Search Algorithm

The analysis can be improved:

Each vertex is colored G exactly once.

Therefore, the inner loop is executed exactly (n − 1) times.

Hence
X
T (n, e) = (3n + 3) + 4(n − 1) + (deg(u) + 2)
u∈V
= (3n + 3) + (4n − 4) + (2e + 2n)
= 9n + 2e − 1.

Compare to
T (n, e) ≤ 5n + 10e + 3.

Remark: Note that e ≤ n(n − 1)/2.

Since the graph is connected, e ≥ n − 1.

If e = Θ(n), then T (n, e) = Θ(n).

21
 Graphs that are not connected

The BFS algorithm also works for graphs that are not connected.
For such graphs, only the vertices v that are in the same compo-
nent as s will get a value d[v] 6= ∞.

In particular, we can use the array d[ ] at the end of the compu-

tation to decide if the graph is connected.

Alternatively, we can use the array color[ ] or the array pred[ ].

Explain why.

How is the analysis of the BFS algorithm changed if we do not

assume that the graph is connect?

22
We can actually modify BFS so that it returns a forest.
More specifically, if the original graph is composed of connected
components C1, C2 , . . . , Ck then BFS will return a tree corre-
sponding to each Ci .

BF S(s) Start BFS

color[s] = G; d[s] = 0; enqueue(Q, s);
if (Q is nonempty)
{ u = dequeue(Q);
for (each v ∈ adj[u])
if (color[v] == W )
{ color[v] = G;
d[v] = d[u] + 1;
pred[v] = u;
enqueue(C, v);
}
color[u] = B;
} End BFS
for (each vertex u ∈ V ) Initialize
{ color[u] = W ;
d[u] = ∞;
pred[u] = N IL;
}
for (each vertex u ∈ V ) Start Connected Component
if d[u] 6= ∞)
BF S(u);

23
 Correctness of the BFS Algorithm

The correctness of the BFS algorithm consists of the following

two parts.

1. Prove that the BFS algorithm outputs the correct distance

d[v].

2. Prove that the paths obtained by using the array pred[v]

are the shortest.

Since the path constructed with the array pred[v] has length ex-
actly d[v], we need to prove only the first part!

24
 Correctness of the BFS Algorithm

Observations: Any vertex v in Q has a real value d[v] 6= ∞.

For u, v ∈ Q at any time, if d[u] < d[v] then u was discovered

earlier than v and (will be processed) earlier than v.

Proof: No proof is given here. You are encouraged to come up

with your own proof.

Theorem: The BFS algorithm outputs the correct distance d[v].

Proof: See next page.

25
 Correctness of the BFS Algorithm

Proof: By induction on d[v]. If d[v] = 0, then v = s. The

conclusion is true.

Assume that d[v] is the correct distance for all d[v] < i. Consider
the case d[v] = i. If d[v] were not the correct distance, then the
true distance d0[v] < d[v]. We then have two paths:

t .... d[a] = d[v]−1 = i−1

a
v
s b
....
w
d[b] = d’[v]−1 < d[a]
d’[v]−1 < d[v]−1 = i−1

(1) st...a must be a shortest path by induction

hypothesis as d[a]=d[v]−1=i−1<i
(2) sw...b must be a shortest path as it is a
subpath of the shortest path sw...bv
(3) a distinct from b because d[b]<d[a], while
both d[a] and d[b] are true distance
Since d[b] < d[a], b should be processed earlier than a, and
should discover v. This is contrary to that a discovered v.

26