(Chapter 22: Elementary Graph

Introduction to Algorithms

(Chapter 22: Elementary Graph Algorithms)

Kyuseok Shim

Electrical and Computer Engineering

Seoul National University

Outline

 This chapter first shows how we can represent a graph in a computer and then discusses algorithms based on searching a graph using either breadth-first search or depth-first search.

 The chapter next gives two applications of depth-first search:

topologically sorting a directed acyclic graph and decomposing a

directed graph into its strongly connected components.

Graph

 A graph G = (V, E) consists of a set of vertices, V, and a set of edges E.

 Each edge is a pair of (v, w) where v,w in V.

 If the pair is ordered, then the graph is called directed.

 Directed graphs are called diagraph.

Graph

 Vertex w is adjacent to v if and only if (v,w) in E.

 In an undirected graph with edge (v,w), and hence (w,v), w is adjacent to v and v is adjacent to w.

 An edge may have either a weight or cost.

Graph

 A path in a graph is a sequence of vertices v ¹ ,v ² ,…v ^N such that (v ⁱ , v ⁱ⁺¹ ) in E for 1≤i<N

 The length of such a path is the number of edges on the path (N-1)

 A simple path is a path such that all vertices are distinct, except that the first and last could be the same

 A cycle in a directed graph is a path of length at least 1 such

that v ¹ = v ^N

Graph

 A directed graph is acyclic if it has no cycles. (DAG)

 An undirected graph is connected if there is a path from every vertex to every other vertex.

 A directed graph with this property is called strongly connected.

 A complete graph is a graph in which there is an edge between

every pair of vertices.

Representations of Graphs

 Two way to represent a graph G=(V,E)

 Adjacency lists

 Adjacency matrix

Representations of Graphs

1

4

3 2

5

1 2 3 4 5

2 5

1 5 3 4

2 4

2 5 3

4 1 2

1 2 3 4 5

1 0 1 0 0 1

2 1 0 1 1 1

3 0 1 0 1 0

4 0 1 1 0 1

5 1 1 0 1 0

(a) (b)

(c)

(a) Undirected graph G (b) Adjacency-list

(c) Adjacency-matrix

Representations of Graphs

1

5

3 2

4

1 2 3 4 5 6 1 0 1 0 1 0 0 2 0 0 0 0 1 0 3 0 0 0 0 1 1 4 0 1 0 0 0 0 5 0 0 0 1 0 0 6 0 0 0 0 0 1

(a)

(c)

(a) Directed graph G (b) Adjacency-list (c) Adjacency-matrix

6

(b)

Representation of Graphs

 Adjacency matrix:

 O(|V| ² )

 Good for dense graphs

 Adjacency list:

 O(|E| + |V|)

 Good for sparse graphs

Breadth-first Search

Breadth-first Search

 One of the simplest algorithms for searching a graph.

 Systematically explores the edges of G to discover every vertex that is reachable from a distinguished source vertex s.

 Compute the distance (smallest number of edges) from s to each reachable vertex.

 Also, it produces a breadth-first tree.

 For any vertex reachable from s, the simple path in the breadth-first

tree from s to v corresponds to a “shortest path” from s to v in G.

Breadth-first Search

B D

A F

C

E B

D

F A

C E

Breadth-first Search



Expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.



Discover all vertices at distance k from s before discovering any vertices at

distance k+1.

Breadth-first Search



To keep track of progress, breadth-first search colors each vertex white, gray, or black.



All vertices start out white and may later become gray and then black.



A vertex is discovered the first time it is encountered during the search, at which time it becomes nonwhite.



Gray and black vertices, therefore, have been discovered, but breadth-first search distinguishes between them to ensure that the search proceeds in a breadth-first manner.



All vertices adjacent to black vertices have been discovered.

Breadth-first Search

 Breadth-first search constructs a breadth-first tree, initially containing only its root, which is the source vertex s.

 Whenever the search discovers a white vertex v in the course of scanning the adjacency list of an already discovered vertex u, the vertex v and the edge (u, v) are added to the tree.

 In this case, we say that u is the predecessor or parent of v in the breadth-first tree.

 Since a vertex is discovered at most once, it has at most one parent.

Breadth-first Search

 The breadth-first-search procedure BFS below assumes that the input graph G=(V,E) is represented using adjacency lists.

 We store the color of each vertex u ∈ V in the attribute u.color and the predecessor of u in the attribute u.𝜋.

 If u has no predecessor, then u.𝜋 = NIL.

 The attribute u.d holds the distance from the source s to vertex u computed by the algorithm.

 The algorithm also uses a first-in, first-out queue to manage the set of

gray vertices.

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

r s t u

v w x y

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

∞ ∞ ∞

∞ ∞ ∞ ∞

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL NIL NIL NIL NIL NIL NIL}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

∞ 0 ∞ ∞

∞ ∞ ∞ ∞

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL NIL NIL NIL NIL NIL NIL NIL}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

∞ 0 ∞ ∞

∞ ∞ ∞ ∞

r s t u

v w x y

Q = ∅

vertex s r t u v w x y

𝜋 ^{NIL NIL NIL NIL NIL NIL NIL NIL}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

∞ 0 ∞ ∞

∞ ∞ ∞ ∞

r s t u

v w x y

s

Q

vertex s r t u v w x y

𝜋 ^{NIL NIL NIL NIL NIL NIL NIL NIL} 0

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

∞ 0 ∞ ∞

∞ ∞ ∞ ∞

r s t u

v w x y

Q = ∅ u = s

vertex s r t u v w x y

𝜋 ^{NIL NIL NIL NIL NIL NIL NIL NIL}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

∞ 0 ∞ ∞

∞ ∞ ∞ ∞

r s t u

v w x y

Q = ∅

u = s

G.adj[u] = {w, r}

vertex s r t u v w x y

𝜋 ^{NIL NIL NIL NIL NIL NIL NIL NIL}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

∞ 0 ∞ ∞

∞ 1 ∞ ∞

r s t u

v w x y

Q

u = s

G.adj[u] = {w, r}

vertex s r t u v w x y

𝜋 ^{NIL NIL NIL NIL NIL s NIL NIL}

w

1

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 ∞ ∞

∞ 1 ∞ ∞

r s t u

v w x y

Q

u = s

G.adj[u] = {w, r}

vertex s r t u v w x y

𝜋 ^{NIL s NIL NIL NIL s NIL NIL}

w r

1 1

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 ∞ ∞

∞ 1 ∞ ∞

r s t u

v w x y

Q u = s

vertex s r t u v w x y

𝜋 ^{NIL s NIL NIL NIL s NIL NIL}

w r

1 1

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 ∞ ∞

∞ 1 ∞ ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s NIL NIL NIL s NIL NIL}

u = w

r

1

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 ∞ ∞

∞ 1 ∞ ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s NIL NIL NIL s NIL NIL}

u = w

G.adj[u] = {s, t, x}

r

1

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 ∞ ∞

∞ 1 ∞ ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s NIL NIL NIL s NIL NIL}

u = w

G.adj[u] = {s, t, x}

r

1

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

∞ 1 ∞ ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL NIL s NIL NIL}

u = w

G.adj[u] = {s, t, x}

r

1

t

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

∞ 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL NIL s w NIL}

u = w

G.adj[u] = {s, t, x}

r

1

t

2

x

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

∞ 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL NIL s w NIL}

u = w

G.adj[u] = {s, t, x}

r

1

t

2

x

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

∞ 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL NIL s w NIL}

u = r

t

2

x

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

∞ 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL NIL s w NIL}

u = r

G.adj[u] = {s, v}

t

2

x

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

∞ 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL NIL s w NIL}

u = r

G.adj[u] = {s, v}

t

2

x

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL r s w NIL}

u = r

G.adj[u] = {s, v}

t

2

x

2

v

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL r s w NIL}

u = r

G.adj[u] = {s, v}

t

2

x

2

v

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL r s w NIL}

u = t

x

2

v

2

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL r s w NIL}

u = t

x

2

v

2

G.adj[u] = {w, x, u}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL r s w NIL}

u = t

x

2

v

2

G.adj[u] = {w, x, u}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 ∞

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w NIL r s w NIL}

u = t

x

2

v

2

G.adj[u] = {w, x, u}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w NIL}

u = t

x

2

v

2

G.adj[u] = {w, x, u}

u

3

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w NIL}

u = t

x

2

v

2

G.adj[u] = {w, x, u}

u

3

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w NIL}

u = x

v

2

u

3

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w NIL}

u = x

v

2

u

3

G.adj[u] = {w, t, u, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w NIL}

u = x

v

2

u

3

G.adj[u] = {w, t, u, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w NIL}

u = x

v

2

u

3

G.adj[u] = {w, t, u, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 ∞

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w NIL}

u = x

v

2

u

3

G.adj[u] = {w, t, u, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = x

v

2

u

3

G.adj[u] = {w, t, u, y}

y

3

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = x

v

2

u

3

G.adj[u] = {w, t, u, y}

y

3

1 0 2 3

2 1 2 3

r s t u

v w x y

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = v

u

3

y

3

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = v

u

3

y

3

G.adj[u] = {r}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = v

u

3

y

3

G.adj[u] = {r}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = v

u

3

y

3

G.adj[u] = {r}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = u

y

3

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = u

y

3

G.adj[u] = {t, x, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = u

y

3

G.adj[u] = {t, x, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = u

y

3

G.adj[u] = {t, x, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = u

y

3

G.adj[u] = {t, x, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

Q

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = u

y

3

G.adj[u] = {t, x, y}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = y

Q = ∅

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = y Q = ∅

G.adj[u] = {u, x}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = y Q = ∅

G.adj[u] = {u, x}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = y Q = ∅

G.adj[u] = {u, x}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

u = y Q = ∅

G.adj[u] = {u, x}

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

Q = ∅

Breadth-first Search

BFS(G,s)

1. for each vertex u ∈ G.V-{s}

2. u.color = WHITE

3. u.d = ∞

4. u.𝜋 = NIL

5. s.color = GRAY 6. s.d = 0 7. s.𝜋 = NIL

8. Q = ∅

9. ENQUEUE(Q, s) 10. While Q ≠ ∅

11. u = DEQUEUE(Q)

12. for each v ∈ G.adj[u]

13. if v.color == WHITE

14. v.color = GRAY

15. v.d = u.d + 1

16. v.𝜋 = u

17. ENQUEUE(Q, v)

18. u.color = BLACK

1 0 2 3

2 1 2 3

r s t u

v w x y

vertex s r t u v w x y

𝜋 ^{NIL s w t r s w x}

Breadth-first Search

 Loop invariant



At the test in line 10, the queue Q consists of the set of gray vertices

 Although we won’t use this loop invariant to prove correctness, it is

easy to see that it holds prior to the first iteration and that each

iteration of the loop maintains the invariant.

Breadth-first Search

 Loop invariant



At the test in line 10, the queue Q consists of the set of gray vertices.

 Initialization



Prior to the first iteration, the only gray vertex, and the only vertex in Q, is

the source vertex s.

Breadth-first Search

 Loop invariant



At the test in line 10, the queue Q consists of the set of gray vertices.

 Maintenance



Line 11 determines the gray vertex u at the head of the queue Q and removes it from Q.



The for loop of lines 12–17 considers each vertex in the adjacency list of u.



Whenever a vertex is painted gray (in line 14) it is also enqueued (in line

17), and whenever a vertex is dequeued (in line 11) it is also painted black

(in line 18).

Breadth-first Search

 Analysis of running time on an input graph G=(V,E).



Each vertex is enqueued at most once, and hence dequeued at most once.



The operations of enqueuing and dequeuing take O(1) time, and so the total time devoted to queue O(|V|).



Because the procedure scans the adjacency list of each vertex only when the vertex is dequeued, it scans each adjacency list at most once.



Since the sum of the lengths of all the adjacency lists is Θ(|E|), the total time spent in scanning adjacency lists is O(|E|).



The total running time of BFS procedure is O(|V|+|E|).

Breadth-first Search

 Shortest path



Define shortest-path distance δ(s,v) from s to v (s,v∈V) as the minimum number of edges in path from s to v.



No path has δ(s,v) = ∞.

Breadth-first Search

 Lemma 22.1



Let G=(V,E) be a directed or undirected graph, and let s∈V be an arbitrary vertex. Then, for any edge (u,v)∈E, δ(s,v) ≤ δ(s,u)+1.

 Proof



If u is reachable from s, then so is v.



The shortest path from s to v cannot be longer than the shortest path from s to u followed by the (u,v).



If u is not reachable from s, δ(s,u) = ∞.

Breadth-first Search

 Lemma 22.2



Let G=(V,E) be a directed or undirected graph, and suppose that BFS is run on G from a given source vertex s∈V. Then upon termination, for each vertex v∈V, the value v.d computed by BFS satisfies v.d ≥ δ(s,v)

 Proof



We use induction on the number of ENQUEUE operations.



Inductive hypothesis : v.d ≥ δ(s,v) for all v∈V



Basis : s.d=0= δ(s,s) and v.d= ∞ ≥ δ(s,v) for all v∈V-{s} in line 9

Breadth-first Search

 Lemma 22.2



Let G=(V,E) be a directed or undirected graph, and suppose that BFS is run on G from a given source vertex s∈V. Then upon termination, for each vertex v∈V, the value v.d computed by BFS satisfies v.d ≥ δ(s,v)

 Proof



We use induction on the number of ENQUEUE operations.



Inductive hypothesis : v.d ≥ δ(s,v) for all v∈V



Inductive step : A white vertex v discovered during the search from u.



v.d = u.d+1 (from line 15)

≥ δ(s,u)+1 (from the induction hypothesis)

≥ δ(s,v) (by Lemma 22.1 (δ(s,v) ≤ δ(s,u)+1))

.

Breadth-first Search



Lemma 22.3



Suppose that during the execution of BFS on a graph G=(V,E), the queue Q contains the vertices <v

,v

,…,v

>, where v

is the head of Q and V

is the tail. Then,

v

.d≤v

.d+1 and v

.d≤v

.d for i=1,2,…,r-1



Proof



The proof is done by induction on the number of queue operations.



Basis : Initially, when the queue contains only s, the lemma certainly holds.



For the inductive step, we must prove that the lemma holds after both dequeuing and

enqueuing a vertex.

Breadth-first Search



Lemma 22.3



Suppose that during the execution of BFS on a graph G=(V,E), the queue Q contains the vertices <v

,v

,…,v

>, where v

is the head of Q and V

is the tail. Then,

v

.d≤v

.d+1 and v

.d≤v

.d for i=1,2,…,r-1



Proof



Inductive hypothesis : v

.d≤v

.d+1 and v

.d≤v

.d for i=1,2,…,r-1



Inductive step – dequeuing



If the head v

of the queue is dequeued, v

becomes the new head.



By hypothesis, v

.d≤v

.d, and v

.d≤v

.d+1≤v

.d+1.



The remaining inequalities are unaffected.

Breadth-first Search



Lemma 22.3



Suppose that during the execution of BFS on a graph G=(V,E), the queue Q contains the vertices <v

,v

,…,v

>, where v

is the head of Q and V

is the tail. Then,

v

.d≤v

.d+1 and v

.d≤v

.d for i=1,2,…,r-1



Proof



Inductive hypothesis : v

.d≤v

.d+1 and v

.d≤v

.d for i=1,2,…,r-1



Inductive step – equeuing



When enqueue a vertex v (line 17), it becomes v

.



At that time, we have already removed vertex u.



By the hypothesis, the new head v

has v

.d ≥ u.d and so v

.d = v.d = u.d+1 ≤ v

.d+1.



From the hypothesis, we also have v

.d ≤ u.d+1, and so v

.d ≤ u.d+1 = v.d = v

.d.



The remaining inequalities are unaffected.

Breadth-first Search

 Corollary 22.4



Suppose that vertices v _i and v _j are enqueued during the execution of BFS, and that v _i is enqueued before v _j . Then v _i .d≤v _j .d at the time that v _j is enqueued.

 This corollary shows that the d values at the time that vertices

are enqueued are monotonically increasing over time.

Breadth-first Search

 Corollary 22.4



Suppose that vertices v _i and v _j are enqueued during the execution of BFS, and that v _i is enqueued before v _j . Then v _i .d≤v _j .d at the time that v _j is enqueued.

 Proof



Immediate from Lemma 22.3 and the property that each vertex

receives a finite d value at most once during the course of BFS.

Breadth-first Search

 Theorem 22.5 (Correctness of BFS)



Suppose that BFS discovers on G=(V,E) from a given source vertex s∈V. Then, during execution, BFS discovers every vertex v∈V that is reachable from the source s, and upon termination, v.d=δ(s,v) for all v∈V. Moreover, for any v≠s that is reachable from s, one of the shortest paths from s to v is a shortest path from s to v.

followed by the edge (v.,v)

Breadth-first Search

 Proof



Assume, some vertex receives a d value not equal to its shortest path distance. Let v be the vertex with minimum δ(s,v) that receives such an incorrect d value. By Lemma 22.2, v.d>δ(s,v) . Vertex v must be reachable from s (if not, δ(s,v) = ∞ ≥ v.d). Let u be the vertex immediately preceding v on a shortest path from s to v, so that δ(s,v)=δ(s,u)+1.



Because δ(s,u) < δ(s,v), and because of how we choose v, u.d= δ(s,u).

Thus, we have v.d>δ(s,v) =δ(s,u)+1=u.d+1



Now, consider the time dequeuing u from Q(line 11)



If v is white : v.d=u.d+1



If v is black : Already removed. By Corollary 22.4 v.d≤u.d.



If v is gray : It was painted upon dequeuing some vertex w, which was removed from Q earlier than u, and v.d=w.d+1. By Corollary 22.4

w.d≤u.d, then v.d≤u.d+1



Since every case contradicts v.d>u.d+1, v.d=δ(s,v) for all v∈V.

Breadth-first Search

 Proof (continued)



All vertices reachable from s must be discovered, for otherwise they would have ∞=v.d>δ(s,v).



To conclude the proof of the theorem, observe that if v. = u, then v.d = u.d + 1.



Thus, we can obtain a shortest path from s to v by taking a

shortest path from s to v. and then traversing the edge (v.,v).

Breadth-first Search

 Breadth-first trees ( BFTs)



BFS builds a breadth tree (BFT)



The tree is represented by the  field in each vertex



For a graph G=(V,E) with source s, define the predecessor subgraph of G as G _ =(V _ ,E _ ), where

V _ ={v ∈ V | v. ≠ NIL} U {s} and E _ ={(v., v) | v ∈ V _ -{s}}



Predecessor subgraph G _ is a BFT, if (1) V _ consists of the vertices

reachable from s and, (2) for all v∈ V _ , the subgraph G _ contains a unique simple path from s to v that is also a shortest path from s to v in G.



A breadth-first tree is a tree, since it is connected and |E| = |V| - 1 (see Theorem B.2).



Edges in E _ are called tree edges.

Properties of Free Trees

 Theorem B.2



Let G=(V,E) be an undirected graph. The following statements are equivalent.



G is a (free) tree.



Any two vertices in G are connected by a unique simple path.



G is connected, but if any edge is removed from E, the resulting graph is disconnected.



G is connected, and |E| = |V| - 1.



G is acyclic, and |E| = |V| - 1.



G is acyclic, but if any edge is added to E, the resulting graph

contains a cycle.