Welcome to Lesson 17!

Announcements

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

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                  

Enqueue(Q,s)

while(Q is not empty)

x = front of Q

Dequeue(Q,x)

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:

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

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

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

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
  

• Don't forget to use the following chart and to darken the lines of the BFS tree that results from tracing the graph

Queue:

BFS Activity

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