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?


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.


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                  

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:

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
B
 W
-1 NIL
C  W-1 NIL
D
  W-1 NIL
E  W -1NIL
 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.


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


bfs_2_lvl

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
 W
-1 NIL
2
  W-1 NIL
3
  W-1 NIL
4
  W -1NIL
 5  W -1 NIL
 6  W-1 NIL
 7  W -1NIL
 8  W -1NIL

Queue:


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
B
 W
-1 NIL
C
  W-1 NIL
D
  W-1 NIL
E
  W -1NIL
 F  W -1 NIL
 G  W-1 NIL
 H  W -1NIL

Queue:


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