McGill University:
School of Computer Science
Winter 1997 Class Notes for
308-251B

DATA STRUCTURES AND ALGORITHMS

Topic #27: GRAPHS:BREADTH FIRST SEARCH


Introduction

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


BFS-Traversal of a Tree in O(|V|+|E|)



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.


Additional Information at Each Node

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.

BFS Algorithm

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

For each vertex u do :
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 Neighbors v of u Do :
If color[v] = WHITE then
color[v] <- GREY
d[v]<- d[u]+1
p[v] <- u
enqueue(Q,v)
color[u] <- BLACK



FIGURE 3

Complexity of the Algorithm

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.


Applications

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

Shortest Paths

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

Bushfire Algorithm

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.


Java Applet

The Barcelona metro

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.

Source Code


Links to Related Material

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.


References


Web page creators

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

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.

Return to top of page.