Welcome Back!

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
  • Project Report 4 due
  • Discuss Project Report 5
  • Final Exam 1 Week from today
    • Will be slightly longer than a midterm
    • Cumulative through Graphs and Merge Sort
    • Final Exam Review Posted (with answer key) - (Non Merge Sort) Sorting Questions optional
  • Quiz after the break - Graph definitions and BFS
  • Tomorrow's online office hours start and end one half hour early.



Review Activity

  • Trace BFS on the graph using 6 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.
  • 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 Big-O Run-time:

  • The Big-O run-time of DFS, like BFS, is considered to be O(|V| + |E|) 
  • Where |V| = number of vertices in the Graph and |E| is the number of edges.
  • Every vertex and every edge will be explored in the worst case with DFS.


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

ملف:Disconnected simple graph.svg

  • 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).
 Vertex Adjacency List
 Color Discover Finish Parent
 0 W
 -1-1
  NIL
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 -1NIL
 8  W-1
-1
NIL

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

figure4051

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

~Have a Great Weekend!~