Welcome to Lesson 17!

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?

  • Midterm 2 Results:
    • As: 30 (1 100% score)
    • Bs: 10
    • Cs: 2
    • Ds: 0
    • Fs: 0
    • Return midterms in last 5 minutes of class
  • Quiz 6 Wednesday on Graphs - last quiz!
  • Lab 8 grades posted by next class
  • Project Report 4 due one week from today
  • Everyone should be working on your project now!
    • All teammates should be able to show progress they have made
    • If someone has not yet started their part of the project it is time to be worried
    • Consider assigning that person's part of the project to other(s) on the team
  • Women in CS meeting on Wednesday at 12:30 - Intel Speaker!

Review Activity
With a partner, answer the questions below:

  • Are the below graphs
    • cyclic or acyclic?:
    • directed or undirected?
    • connected or disconnected?

Graph 1:

Image source.

Graph 2:

Wrap up Graph Intro Lesson

Breadth First Search

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

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                  


while(Q is not empty)

x = front of Q


for all y in adj[x]

if color[y] == white

color[y] = grey

distance[y] = distance[x] + 1

parent[y] = x

Enqueue(Q, y)

color[x] = black

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.

BFS Example

  • Let's trace through this algorithm with an example.
  • Consider the following graph G1:

Graph 2

  • 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 following chart to help organize us:

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

Queue: A


  • 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


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


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.


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

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.

Activity: BSF on Graph G1

  • While the professor is tracing through the BFS example on G1, update your own paper.

BFS by Level


Image source.

BFS Activity

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

ملف:Disconnected simple graph.svg

  • 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 NIL
  W-1 NIL
  W-1 NIL
  W -1NIL
 5  W -1 NIL
 6  W-1 NIL
 7  W -1NIL
 8  W -1NIL


BFS Activity

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

Image result for breadth first search

 Vertex Adjacency_List[]
 Color[] Distance[] Parent[]
 A W
 -1 NIL
-1 NIL
  W-1 NIL
  W-1 NIL
  W -1NIL
 F  W -1 NIL
 G  W-1 NIL
 H  W -1NIL


Wrap Up
  • With your partner, answer the questions from today's learning objectives