Learning Objectives
- Describe the DFS algorithm in your own words.
- How does DFS differ from BFS?
- What are some applications of DFS and BFS?
1. 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.
- The book-keeping 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).
1.1. DFS AlgorithmDFS(G) for all x in V(G) color[x] = W parent[x] = NIL discovery_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[x] = ++time for all y in adj[x] if color[y] == W parent[y] = x Visit(y) color[x] = B finish[x] = ++time
1.2. 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
1.3. DFS Example- Let's trace through this algorithm with an example.
- Consider the below graph:
- Take a sheet of paper and recreate the following table.
- Also draw the corresponding graph on your paper

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.
DFS Forest- The path that the algorithm takes through the graph creates a DFS forest (potentially multiple trees).
2. DFS Activity
2.1. First Graph
- Trace DFS on the following graph, including the DFS forest, by processing the vertices in ascending order (smallest to largest)
Image source.
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
|
2.2. Second Graph
- Trace DFS on the following graph, including the DFS forest, by processing the vertices in ascending order (smallest to largest)
Image source.
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 |
3. Applications of DFS and BFS

Image source.
Cycle detection Shortest Path
Connected Components Connectivity Testing
3.1. 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 - Answer the review questions on Canvas from today's learning objectives
~Have a Great Day!~
|
|