• Describe the DFS algorithm in your own words.
• How is it different from BFS?
  
• What are some applications of DFS and BFS?
  

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

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

• A comparison of BFS and DFS.

Edge Classification

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

Image source.

• Back edges indicates a cycle in the graph!