An introduction to Depth First Search

mgcadmin 16-09-2021

Depth first search is a tree and graph search and traversal method frequently encountered and often used as a building block to more complex algorithms.

What is Depth First Search?

Depth first search is a tree and graph search and traversal method frequently encountered and often used as a building block to more complex algorithms. It's stack based nature lends well to recursive implementations and thus it is somewhat easier to implement than Breadth First Search.

Applications

Because of the recursive nature of Depth First Search it is uniquely qualified to implement 'backtracking' algorithms. Backtracking algorithms are useful in many practical applications, such as solving a Sudoku, figuring out a maze, and other "constraint programming" problems. 2 famous examples of depth first search based algorithms are Donald Knuth's "Algorithm X", and solving the n-Queens problem.

Pros and Cons

Depth First Search is very easily implemented in any programming environment that supports recursion. re: All modern environments. Even in environments that have strict limitations on resources, depth first search can be implemented iteratively with the help of a LIFO stack data structure to replace the call stack used in recursive implementations.

Unfortunately, DFS may necessitate processing a vast amount of nodes before finding a target that was in fact very close, but on a seperate branch which a Breadth First Search would have found sooner. Due to DFS continuing as far down a branch as possible before turning around(i.e. searching DEPTH FIRST...) it has the potential in infinite trees/graphs to wander down a branch and never come back....

Don't let that dissuade you, as mentioned above, depth first search has PLENTY of excellent applications that make it a must learn algorithm.

DFS For Tree Traversal

Because of its easy implementation with recursion Pre-, Post-, and In-order traversal of Binary Trees can be accomplished in less than 5 lines of code, with simple changes to the ordering of functions being the only difference between them:

void preOrderDFS(struct treeNode& x)
{
  if (x != NULL)
  {
     /*
     code to process node goes here
     */
     preOrder(x->left);
     preOrder(x->right);
  }
}

void inOrderDFS(struct treeNode& x)
{
  if (x != NULL)
  {
     inOrderDFS(x->left);  
     /*
     code to process node goes here
     */
     inOrderDFS(x->right);
  }
}

void postOrderDFS(struct treeNode& x) 
{ 
  if (x != NULL) 
  { 
    postOrderDFS(x->left); 
    postOrderDFS(x->right);
    /* code to process node goes here */  
  } 
}

In Graphs

Depth First Search when applied to graphs though more complicated than tree traversal is still easily implemented with recursion. The main difference is that unlike in trees, for graphs we have to keep track of which vertexes have been visited in order to avoid being caught in an endless loop if the graph nodes contain a cycle. Since we used the adjacency list representation of graphs in the Breadth First Search article, well use the adjacency matrix representation of a graph for our DFS. If you need a refresher on the adjacency matrix representation of a graph, head on over to my article on Representing Graphs with the C++ STL.

The following code implements a recursive Depth First Search traversal of the adjacency matrix representation of a graph:

void depthFirstSearch(Graph& g, char v, char u, std::map<char, bool>& seen)
{
  cout<<"Visiting: "<<v<<"\n";
  seen[v] = true;
  if (v == u)
  {
    cout<<"Found!\n";
    return;
  }
  for (auto c = 1; c < g.V; c++)
  {
    char child = (char)(c+'A'-1);
    if (seen[child] == false && g.adjMatrix[v-'A'+1][c] > 0)
    {
      depthFirstSearch(g, child, u, seen);
    }
  }
}

void dfs(Graph& g, char v, char u)
{
  std::map<char, bool> seen;
  depthFirstSearch(g, v, u, seen);
}

We'll be using the following driver program and the Graph class covered in the previously mentioned Graph article to test our Depth First Search:

int main()
{
  Graph G(6);
  G.addEdge('A', 'B', 6);
  G.addEdge('A', 'C', 7);
  G.addEdge('A', 'E', 2);
  G.addEdge('B', 'C', 5);
  G.addEdge('C', 'E', 5);
  G.addEdge('D', 'E', 4);
  G.addEdge('D', 'F', 1);
  G.addEdge('E', 'F', 2);
  G.addEdge('F', 'A', 3);
  G.showAdjMatrix();
  dfs(G, 'A', 'D');
  return 0;
}

Output:

  A B C D E F 
A 0 6 7 0 2 3 
B 6 0 5 0 0 0 
C 7 5 0 0 5 0 
D 0 0 0 0 4 1 
E 2 0 5 4 0 2 
F 3 0 0 1 2 0 

Visiting: A
Visiting: B
Visiting: C
Visiting: E
Visiting: D
D Found!

Full source code for the examples in this article are available on my github at:

https://github.com/maxgoren/examples/blob/main/graphing-dfs.cpp

---