Algorithm - Depth First Search (DFS)

Depth-first-search (DFS) is an algorithm used to traverse graphs. DFS starts at a given vertex visits all the vertices down to the last vertex, then backtracks to the vertex and visits all the vertices under the most “recent” ancestor.

For example, if the graph is a tree structure and the `starting vertex is the root, DFS will visit all the vertices down to the leaf. This is followed by the most recent vertex (that let to the leaf) and visit all vertices the remaining branches.

DSF example of traversing leaf vertexes of the tree first.

Applications of DFS

  • Great at exploring every possible outcome of a particular problem. (e.g.: Finding path out of a maze)
  • Does poorly in situations where the tree / graph is infinitely deep.
  • Can detect Directed Acyclic Graphs (DAG - detect cyclic graphs)
  • Topological sorting
  • Edge classification - evaluate vertex distance/relation.

Topological sort

Topological sort only works for directed acyclic graphs (DAG). A topological sort is the reverse output of a DFS.

Edge Classification

Another useful use of DFS is to perform Edge Classification. Edge classification is possible in DFS because of the way DFS traverses the depth of the vertex’s descendant nodes. Below is a table of some Edge classification types:

Graph showing different Edge types.

Edge Description
Tree Edge to a new Vertex but is not part of the DFS tree.
Forward Edge to descendant of tree
Backward Edge to ancestor that is not part of the DFS tree
Forward Edge to descendant of tree
Cross Edge to descendant of another tree

Detecting Edge Types…

To help identify Edge types, we track the processing start_time and finish_time of a vertex. The start and finish time of a vertex are typically added as properties to a vertex. (can also track separately, (less common))

The start and finish time gives an indication of the order of a vertex in th DFS, which helps differentiate the different Edge types. Below shows how we can differentiate the different edge types:

Shows how we can differentiate different Edge types in DFS.

Tree Edges:

  1. Navigate to a New vertex has not been visited before (not part of DFS tree).
  2. The new Vertex has an ancestor previously directly traversed.

Backward Edges:

  1. Navigating to a vertex already seen.
  2. Vertex we are navigating to is an ancestor of the vertex we are navigating form.
  3. vertex we are navigating form finish_time == null.

Forward Edge:

  1. Navigating to a vertex already seen.
  2. from_vertex.start_time < to_vertex.start_time (to_vertex processed after from_vertex)

Cross Edge:

  1. Navigating to a vertex already seen.
  2. from_vertex.start_time > to_vertex.start_time (to_vertex processed earlier)

DFS Edge Classification

Undirected Graphs

Undirected graphs cannot have Forward edges or Cross edges (for same reasons):

Undirected Graph: C leads back to A which would make C-> a backward edge.

Implementation

DFS traversal of a tree graph from root
Stack implementation of DFS
DFS detecting acyclic graphs.

Time Complexity

DFS visits all the edges of every vertex reachable, so the time complexity of traversing all the edges of all the vertexes in a graph depends on the size of the Adj. list for the graph.

Adj(V)=O(E)Adj(V) = O(E)

For DFS to be complete, we have to ensure all vertexes are also checked. so the total time complexity of running DFS against a graph is linear time …

O(V+E)O(V + E)

Edge Classifications