Welcome to Lesson 16!


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?


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


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)

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


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.

Graph 2



 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.

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.

1.5. BFS by Level


bfs_2_lvl

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

ملف:Disconnected simple graph.svg


 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:


2.2. Second Graph

  • Trace BFS on the following graph, using A as the source vertex
connected, undirected graph with 8 vertices


 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

  • Answer the review questions for this lesson on Canvas

Have a Great Day!