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

 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

• 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