Welcome Back!

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 across the graph rather than down each path, hence its name.
• 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 will be explored in the worst case when running BFS.

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 on G1:

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:

Depth First Search

• Depth First Search (DFS) is another algorithm for traversing or searching a Graph.
• Unlike BFS, however, DFS does not provide us with a solution to the SSSP problem.
• The algorithm recursively traverses the depth of the Graph (downward), rather than its breadth (across).
• DFS creates what is called a DFS forest, which provides us with useful information about the edges in the Graph.

DFS Algorithm

DFS(G)

for all x in V(G)

    color[x] = W

    parent[x] = NIL

    discover_time[x] = -1

    finish_time[x] = -1

time = 0

for all x in V(G)

    if color[x] == W

        Visit(x)

Visit(x)

color[x] = G

discover_time[x] = ++time

for all y in adj[x]

    if color[y] == W

        parent[y] = x

        Visit(y)

color[x] = B

finish_time[x] = ++time

DFS Big-O Run-time:

• The Big-O run-time of DFS, like 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 will be explored in the worst case with DFS.

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

• The book-keeping involved with DFS is also somewhat different than BFS.
• Here, we keep track of start and finish times of vertices, in addition to colors and parents (no distances).
  

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

Discover Time (1 - 2n)

• The time at which the vertex was first discovered (colored gray).
• Initialized to 0
  

Finish Time (1 - 2n)

• The time at which the vertex was finished (turned black).
• Initialize to 0
  
  

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 root of the graph (or connected component).
  

A Word on the Lack of a Source Vertex

• Since we are not trying to find a shortest path here, there is no source vertex.
• Instead, we always start at the "root" of the graph, which in practice is we usually progress in ascending or descending order.

Group Activity

• 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 DFS algorithm is applied.
• While the professor is tracing through the DFS example on G1, update your own paper.
• Also fill in the DFS forest.
  

Group Activity

• On a new sheet of paper, trace DFS on the following graphs.
  
• For credit, you need to trace the values on the table as shown during the lesson.
• You should also create the DFS forest.
  
• Refer to the algorithm when in doubt.
  
• Process the vertices in ascending order.
• When you are finished, think to yourself: How would I handle this disconnected graph if I applied the BFS algorithm?
  

Graph 1:

Graph 2:

Image source.

Applications of DFS and BFS

Image source.

Cycle detection                                  Shortest Path

Connected Components                           Connectivity Testing

• A comparison of BFS and DFS.

Edge Classification

Gray to White       Gray to Black             Gray to Gray                Gray to Black

Image source.

• Back edges indicate a cycle!