School of Computer Science

Winter 1997 Class Notes for 308-251B

In the last lecture, depth first search was covered. In this
page, we will introduce another way of traversing a
graph
: the **Breadth First Search (BFS)**. Like the
Depth First Search,
BFS can be implemented in O(|V|+|E|) time.
It also produces a tree , in this case a BFS tree. Figure.1 shows the difference between a DFS tree and a BFS tree.

FIGURE.1

FIGURE. 2

Given a graph G = (V,E) and a distinct source vertex, **s** (black
node in Figure 2), first visit all the neighbours
(distance = 1 -- blue nodes in Figure 2), and then those at distances
2 (red nodes), then those at distance 3 (yellow nodes), etc.
These are the shortest distances to **s**. (Note that the distance,
or pathlength,
is the number of edges.) We have
seen something similar to this in tree traversals. It is a queue structure.

Each node, **u**, has three additional attributes:

**d[u]**:- Shortest distance from vertex u to source
**s**. **p[u]**:- Parent of u in BFS tree.
**Colour[u]**:-
*white*: unprocessed (not yet visited).

*grey*: being processed.

*black*: processed.

The following is the algorithm for a Breath First Search of a graph. Q is a regular queue.

For each vertexudo :

d[u] <- infinity

color[u] <- WHITE

p[u] <- NIL

d[s] <- 0

color[s] <- GRAY

enqueue(s,Q)

While not empty (Q) do :

u<- dequeue (Q)

for All NeighborsvofuDo :

If color[v] = WHITE then

color[v] <- GREY

d[v]<- d[u]+1

p[v] <-u

enqueue(Q,v)

color[u] <- BLACK

FIGURE 3

The while loop is repeated once for all vertices . Therefore
this part requires |V| time . The statement: If color[**u**] = WHITE
is repeated for every neighbor of **u** . Since the sum of all
neighbors is 2|E|, this part is done 2|E| times . The line:
color[**u**] = BLACK is done |V| times.
Therefore the running time of the BFS algorithm is O(|V| + |E|), which is the same running time
as the Depth First Search.

BFS is an archetype for many important graph algorithms, and thus has several applications. It is used to find the shortest path in networks and is also used in implementations of the Bushfire algorithm (see below).

These are covered in a later lecture. To go that lecture click here.

To make a character into boldface, each pixel adjacent every pixel of the original character would have to be blackened. Therefore, an algorithm which would find the neighbours of the pixels precisely would be needed. The BFS is a good, efficient way of finding each of the neighbours of the pixels so that they may be blackened.

Start a Bushfire along the character at time = 0 and have
it spread uniformly. Each pixel in the
character is a source vertex, **s**. The bushfires start at the
vertices with d[**s**]=0, thus at each pixel in the character. Use a BFS tree and put all of the source pixels into the
queue. After a certain time interval,
all the pixels with d[u] = 1 will be found.

The PathFinder applet uses a BFS tree to find the shortest location between two metro stations on the Barcelona Metro. Simply enter the place where you are in the location field, and your desired destination, and the PathFinder applet will find the fastest route for you.

The applet builds a BFS tree with the current location as Source. Each station is an object, and after the creation of the BFS tree, each of the nodes has pointers to their parents. The program simply follows the pointers from the destination to the Source which gives the shortest path. It is implemented using "dummy" nodes in between real stations to allow for varying distances, but could easily be rewritten using a shortest paths algorithm such as Dijkstra's which is covered in the next lecture.

You may have to resize the window to fit the entire diagram onto the applet.

University of Dundee: CS202: Breadth First Search | Breath First Traversal |

Sugihara's Lecture Notes: BFS | |

OBerlin College: Breadth First Search | An excellent interactive page with links to other graph-related topics. |

- CORMEN, Thomas H., and LEISERSON, Charles E. and RIVEST, RONALD L.,
__Introduction to Algorithms__, The Massachusetts Institute of Technology, Cambridge, Massachusetts, 1990. Section 23.2 - WEISS, MarkAllen,
__Data Structures and Algorithm Analysis in C__The Benjamin / Cummings Publishing Company , Inc., 1992. Section 9.1 - STANDISH, Thomas A.,
__Data Structures, Algorithms & Software Principles in C__, Addison Wesley Publishing Company, 1995, Section10.4 - DROZDEK, Adam, and SIMON Donald L.,
__Data Structures in C__, PWS Publishing Company, 1995, Section 10.2

All comments or suggestions are welcome. If you have any, please send them to one of the creators of this page:

- Ryan Cook (Rcook@po-box.mcgill.ca)
- Robin Merkel (rmerke@po-box.mcgill.ca)
- Sandra Polifroni (snad@cs.mcgill.ca)
- Salah Elatrash (sal@cs.mcgill.ca)

Salah found all the web links and typed the document. Ryan and Robin wrote the Java applet. The text is based on class notes taken by Sandra and Ryan. The figures were drawn using Xfig by Sandra. The Xfig files were grabbed using xv by Sandra. The html was cleaned up a bit by Sandra.

Copyright © 1997, Ryan Cook, Robin Merkel, Sandra Polifroni, Salahudeen Elatrash. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy. Disclaimer: this collection of notes is experimental, and does not serve as-is as a substitute for attendance in the actual class.