Breadth First Search

Overview

There are two basic uniformed (i.e. have no a priori knowledge of solution) approaches for examining graphs: depth first or breadth first.

Breadth first search is preferred if looking for a (solution) vertex close to another vertex with some property. Also, some graphs are infinite or extremely deep (consider chess moves). Depth first search goes deep, getting no solution fast in these graphs, but breadth first search goes one level at a time until finding a solution.

For example, suppose we want to find the path from one city to another, Arad to Fagaras, but had no prior information as to which direction to begin.

Breadth first would travel to all cities adjacent to Arad and continue visiting adjacent cities until Fagaras was reached. We can observe that breadth first will always find a path having the fewest edges, assuming we prevent cycles.

What we've just said is, for finite graphs, breadth first is optimal for edges in the path and complete, meaning it will find a path if one exists from the starting point.

Depth first search might leave out of Arad and perhaps travel through Timisoara and Bucharest before reaching Fagaras. We can observe that depth first is not optimal since much shorter paths exist but it is complete for finite graphs (if cycles are avoided).

Question 22.6 - Would it be possible for breadth first search starting at Arad to reach Neamt on the way to Fagaras? What about depth first?

Breadth first search for Fagaras and beyond

For another example, imagine a chess-playing program. You can think of each possible configuration of the chessboard as a vertex in a graph. The program would do a search in the graph, where moving a particular piece is an edge to another vertex. The program is given, say, 30 seconds to do the search. Using depth first search would allow the program to explore many moves ahead for one particular initial move, but wouldn't allow it to explore any other moves. Breadth first search would allow a variety of moves to be explored, up to several moves ahead to some depth of the search graph but seldom exploring an initial move to its conclusion.

Depth first search is a good way of establishing the nature of the connectivity in a graph. You can build a table out of the results of a search showing which vertices are reachable from which other vertices. Depth first search is also used in determining the strongly connected components of a directed graph. These are all the sub-graphs in which vertices are mutually reachable.

Breadth First Search

Input: Graph G = (V, E), either directed or undirected, and source vertex s Î V.

Output:

v.d = distance (smallest # of edges) from s to v, for all v Î V.

v.p = u such that (u, v) is last edge on shortest path sv;

p is the predecessor subgraph of G produced by BFS formally defined as G_p=(V_p, E_p) where:

• u is v’s predecessor
• set of vertices V_p ={ v Î V : v.p ¹ NIL} È {s}
• set of edges E_p={(v.p, v) : v Î V_p - {s} } forms a tree.

Later, we’ll see a generalization of breadth-first search, with edge weights. For now, we’ll keep it simple.

Idea: Send a wave out from some root vertex, s.

• First hits all vertices 1 edge from s (those vertices directly connected to s).
• From there, hits all vertices 2 edges from s.
• Etc.

Use FIFO queue Q to maintain wave front.

• v Î Q if and only if wave has hit v but has not come out of v yet.

• Mark each vertex when visited to avoid cycles.

Example - Construct tree from undirected graph by constructing p list during BFS.

V={r, s, t, u, v, w, x, y}

E={(r,v), (r,s), (s,w), (w,x), (w,t), (t,x), (t,u), (x,u), (x,y), (u,y)}

Q = FIFO of vertices discovered but not visited

• WHITE - undiscovered
• GRAY - discovered and in queue waiting to be processed
• BLACK - discovered and visited

r s t u v w x y p NIL NIL NIL NIL NIL NIL NIL NIL d ¥ 0 ¥ ¥ ¥ ¥ ¥ ¥	r s t u v w x y p s NIL NIL NIL NIL s NIL NIL d 1 0 ¥ ¥ ¥ 1 ¥ ¥
r s t u v w x y p s NIL w NIL NIL s w NIL d 1 0 2 ¥ ¥ 1 2 ¥	r s t u v w x y p s NIL w NIL r s w NIL d 1 0 2 ¥ 2 1 2 ¥
r s t u v w x y p s NIL w t r s w NIL d 1 0 2 3 2 1 2 ¥	r s t u v w x y p s NIL w t r s w x d 1 0 2 3 2 1 2 3
r s t u v w x y p s NIL w t r s w x d 1 0 2 3 2 1 2 3	r s t u v w x y p s NIL w t r s w x d 1 0 2 3 2 1 2 3
r s t u v w x y p s NIL w t r s w x d 1 0 2 3 2 1 2 3

Question 22.7 After executing BFS,

1. What does x.d mean?
2. What does x.p mean?
3. What is the maximum distance to source s?
4. Trace the path starting at y.p to the source s.
5. Draw the tree rooted at s.

BFS (G, s)   -- post: every vertex that is reachable from s -- is discovered and the BFS tree is created -- in p            Times Cost 1 for each vertex u Î G.V - {s} do |V| O(V) 2    u.color ¬ WHITE |V|-1   3    u.d ¬ ¥ |V|-1   4    u.p ¬ NIL |V|-1     -- Initialize the source vertex and Queue     5 s.color ¬ GRAY 1   6 s.d ¬ 0 1   7 s.p ¬ NIL 1   8 Q ¬ Æ 1   9 Enqueue (Q, s) 1     -- Perform breadth first search     10 while Q ¹ Æ do |V|+1 O(V) 11    u ¬ Dequeue (Q) |V|   12    for each v Î G.Adj[u] do |V|+|E|+1 O(V+E) 13        if v.color = WHITE then |V|+|E|   14           v.color ¬ GRAY |V|   15           v.d ¬ u.d + 1 |V|   16           v.p ¬ u |V|   17           Enqueue (Q, v) |V|   18    u.color ¬ BLACK |V|

1 2 3 4 5 p NIL NIL NIL NIL NIL d ¥ ¥ ¥ ¥ 0 color WHITE WHITE WHITE WHITE GRAY Question 22.8 Execute the BFS on source vertex 5, visiting adjacent vertices at line 12 in numerical order. Draw BFS tree. Count the number of times Line 12 is executed. Did it agree with |V|+|E|+1?

Loop-invariant - while loop of Lines 10-18

loop invariant: Line 10, the queue Q consists of the set of GRAY vertices (i.e. those that have been discovered but not visited)

initialization: prior to first iteration, Q={s} and s.color = GRAY

maintenance:

• Line 11 removes one GRAY vertex u from Q which will be colored BLACK (i.e. discovered and visited).
• Lines 12-17, any WHITE (i.e. undiscovered) vertex v reachable from u is colored GRAY and inserted at the tail of Q.
• v.d ¬ u.d+1
• v.p ¬ u

termination:

• loop terminates when Q = Æ; no GRAY vertices remain.
• all vertices reachable from a GRAY vertex have been colored BLACK.

Analysis - BFS is O(V+E) due to line 12.

V+E because each V vertex is examined but only the E edges connecting to adjacent vertices: for each v Î G.Adj[u] do, not all the edges of G.

• O(V) because every vertex is enqueued at most once, Line 17.
• O(E) because every vertex is dequeued at most once and we examine (u, v) only when u is dequeued. Therefore, every edge examined at most once if directed, at most twice if undirected.

Note that this is for an adjacency list representation.

Question 22.9

1. Is every vertex visited for an undirected graph? a directed graph? See the graph at right.
2. Give an example that contradicts the statement "every edge is examined in an undirected graph".
3. What is the purpose of the queue? Think about what happens in Lines 12-17.
4. What would be the running time for an adjacency matrix representation? Hint: Consider how edges are represented at right.
5. Run BFS on the graph at right starting at D.
6. Draw the resulting breadth-first tree(s).
7. We stated that is O(V+E). From Question e, is it also W(V+E)?

Shortest paths

• BFS finds the shortest path from source vertex to all other reachable vertices in graph. The text gives a proof of correctness for the BFS algorithm.

Question 22.10 - For the graph below.

1. Suppose we reran BFS with a different source, would the results be the same?
2. What is the distance to s from y?
3. What is the shortest path to s from y?
4. Give an undirected graph that has the shortest path length |V| (i.e. the path includes every vertex).
5. Give an algorithm to print the vertices in the shortest path from any vertex to the source.

	r	s	t	u	v	w	x	y
p	s	NIL	w	t	r	s	w	x
d	1	0	2	3	2	1	2	3