## Learning Objectives

By the end of this class, you should know...
• How do you traverse a graph using the Breadth First Search (BFS) Algorithm?
• What is the SSSP problem?
• How does BFS solve this problem?

• Breadth First Search (BFS) is a Graph Traversal Algorithm that solves the Single Source Shortest Path (SSSP) problem.
• In other words, it finds the shortest path (fewest edges) between a source vertex and any other vertex in the graph.
• BFS traverses vertices and edges, moving across the graph rather than down each path, hence its name.
• Results in a level order traversal
• It also creates a BFS tree which is a subtree of the original graph that is rooted at the source vertex.
• The algorithm uses a Queue, as well as a book-keeping scheme wherein vertices are assigned colors to keep track of which vertices have been visited as the algorithm progresses.

### 1.1. BFS Algorithm

BFS(G, s)

for all x in V(G)

color[x] = white

distance[x] = -1

parent[x] = Nil

color[s] = grey

distance[s] = 0

Enqueue(Q,s)

while(Q is not empty)

x = front of Q

Dequeue(Q,x)

if color[y] == white

color[y] = grey

distance[y] = distance[x] + 1

parent[y] = x

Enqueue(Q, y)

color[x] = black

### 1.2. BFS Big-O Run-time:

• The Big-O run-time of BFS is considered to be O(n + m)
• Where n = number of vertices in the Graph and m = the number of edges.
• Every vertex and every edge (or a subset there of) will be explored in best, worst and average cases.

### 1.3. BFS Example

• Let's trace through this algorithm with an example.
• Consider the following graph G1.
• Suppose that we wish to find the shortest distance from A to any other vertex in our graph.
• In other words, we consider A to be our source vertex.
• Recall that shortest distance means fewest number of edges.
• As we trace BFS on the above graph, we will need to do some book keeping.
• Thus, we should start by drawing the below chart to help organize us.

 Vertex Adjacency_List[] Color[] Distance[] Parent[] A G 0 NIL B W -1 NIL C W -1 NIL D W -1 NIL E W -1 NIL F W -1 NIL

Queue: A

#### Colors

• Here the Color column for each vertex will be set to one of three possible values: white, grey or black.
• White indicates that a vertex has not been processed
• Grey indicates that a vertex is in process
• Black indicates that a vertex is finished being processed

#### Distance

• The distance column indicates distance to the source vertex
• The distance to the source from the source is 0, so we can immediately assign it a value.
• Other vertices are assigned the value of -1 to start. This value will be updated as the algorithm progresses.

#### Parent

• The parent column indicates which vertex immediately proceeded the current vertex in the path from the source to the current vertex.
• NIL indicates that a parent has not been assigned.
• However, in the case of the source vertex, the value of NIL will never be updated.

#### Queue

• The Queue will maintain an order in which the vertices need to be processed.
• The Queue is pre-filled only with the value of the source.
• As vertices are processed, they are added to the back of the queue.
• When they are finished being processed, they are dequeued.

#### A Word on the Source Vertex

• The source vertex is indicated in purple.
• I initialize it differently than the other vertices as it is already in progress as the algorithm starts
• Note that I could apply the BFS algorithm using any vertex in my Graph as the source.

### 1.4. Review of Adjacency List Representation of a Graph

• Take a sheet of paper and recreate the table above.
• Also draw the corresponding graph on your paper
• Then, fill in the adjacency list for each of the vertices.
• Hold onto the paper when you are finished, as you will fill in the table as the BFS algorithm is applied.

Image source.

## 2. BFS Activity

### 2.1. First Graph

• Trace BFS on the following graph, using 8 as the source vertex
• Don't forget to use the following chart and to darken the lines of the BFS tree that results from tracing the graph

 Vertex Adjacency_List[] Color[] Distance[] Parent[] 0 W -1 NIL 1 W -1 NIL 2 W -1 NIL 3 W -1 NIL 4 W -1 NIL 5 W -1 NIL 6 W -1 NIL 7 W -1 NIL 8 W -1 NIL

Queue:

### 2.2. Second Graph

• Trace BFS on the following graph, using A as the source vertex

 Vertex Adjacency_List[] Color[] Distance[] Parent[] A W -1 NIL B W -1 NIL C W -1 NIL D W -1 NIL E W -1 NIL F W -1 NIL G W -1 NIL H W -1 NIL

Queue:

## Wrap Up

• Answer the review questions for this lesson on Canvas

Have a Great Day!