Learning Objectives
 Describe the DFS algorithm in your own words.
 How is it different from BFS?
 What are some applications of DFS and BFS?
Announcements
 Return Project Report 3
 Project Report 4 due Monday
 Average Peer Evaluation scores posted
 Talk to your teammates if your score was not as high as anticipated
 Ask them, what should I be doing to raise my score on the next peer evaluation
 Peer Evaluation 2 weighted at 75%
 Final exam one week from today
 Cumulative! Review old quizzes and midterms
 Final exam review posted with example questions on graphs and sorting algorithms (topic of next class)
 Keep working on your projects!
Review Activity
 Write the adjacency list representation of the below graph
 Trace BFS on the graph using 1 as the source vertex.
 First try to trace the algorithm directly on the graph (without the chart)
 Then, use the chart presented last class to keep track of each step of the algorithm.
 Draw the BFS tree that results from tracing BFS on the below graph.
Image source.
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.
 Instead, it is used for tasks such as cycle detection, detecting borders in image recognition, task scheduling, solving puzzles such as mazes, and more!
 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 time = 0 for all x in V(G) if color[x] == W Visit(x)
Visit(x) color[x] = G discover[x] = ++time for all y in adj[x] if color[y] == W parent[y] = x Visit(y) color[x] = B finish[x] = ++time
DFS BigO Runtime:  The BigO runtime of DFS, like BFS, is considered to be O(n + m)
 Where n = number of vertices in the Graph and m is the number of edges.
 Average and worst case with DFS will result in ~exploring all vertices and edges
DFS Example Let's trace through this algorithm with an example.
 Consider the following graph:
 The bookkeeping involved with DFS is also somewhat different than BFS.
 First, there is no source vertex. Instead we select an ordering of vertices, such as ascending or descending and proceed through the algorithm in this predetermined order.
 Here, we keep track of start and finish times of vertices, in addition to colors and parents (no distances).
Vertex  Adjacency List
 Color  Discover  Finish  Parent  1   W
 1  1
 NIL  2
  W
 1
 1  NIL  3
  W  1  1  NIL  4
  W  1
 1  NIL  5
  W  1  1
 NIL
 6   W  1  1  NIL  7   W  1
 1  NIL  8
  W  1  1  NIL
 9   W  1
 1
 NIL

Colors
 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 through the graph.
 NIL indicates that a parent has not been assigned.
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: More DFS Practice
 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
Edge Classification Gray to White Gray to Black Gray to Gray Gray to Black
Image source.  Back edges indicates a cycle in the graph!
Wrap Up  With your partner, answer the questions from today's learning objectives
Upcoming Assignments  Final Exam one week from today!
 Work on your course projects!
~Have a Great Weekend!~
