Depth first search algorithm

Depth first search is an algorithm for graph traversal. DFS explores as far as possible along an edge of the graph before backtracking. This means it goes deep into the graph in one neighboring node direction before exploring other neighboring nodes.

To explain DFS in detail, lets take an example python matrix — which is a graph. Below we have an example matrix.

matrix = [['A','O','O','D'],
          ['P','G','N','M'],
          ['B','C','C','M']]

To understand any algorithm, picking a problem is a good approach. Let us a pick a problem.

Problem: we need to find if the matrix can form the word “GOOD” by starting at an edge, traversing through its neighbors, and not repeating any edge.

Solution: we can find if the word “GOOD” can be formed by attempting to start at each node of the matrix to check if it has the first (or current) alphabet, then checking if each of the 4 neighbor nodes is the next alphabet, and then repeating that until full length of the word is reached — which means we have found the word OR break if we are visiting an already visited node OR if we are exceeding the boundary of the matrix.

Make above in bullet points.

def find_word(i, j, index):

  # check if we have reached end of the word
  if index >= len(word):
    return True
  
  # check if we have crossed the boundaries of the matrix
  if i >= rows or i < 0 or j >= cols or j < 0:
    return False

  # check if we have already visited the node
  if (i,j) in visited_nodes:
    return False

  # add node as visited
  visited_nodes[f'{i,j}'] = 1

  # recursively traverse through neighbor nodes
  # and check if the word can be formed
  # if thew word is found, return True
  if find_word(i+1, j, index+1) or
     find_word(i, j+1, index+1) or
     find_word(i-1, j, index+1) or
     find_word(i, j-1, index+1) or:
     return True

  # backtrack, and remove the node as visited
  visited_nodes[f'{i,j}'] = 0
  
  return False

def traverse_matrix(matrix):

  # get size of matrix
  rows, cols = len(matrix), len(matrix[0])
  visited_nodes = {}
  word = 'GOOD'
  index = 0

  for i in range(rows);
     for j in range(cols):
       if matrix[i][j] == word[index] and find_word(i,j, index+1):
         return True

  return False

Practical applications of DFS

DFS can be used for we crawling. In web crawling, the crawler traverses through each hyperlink in the web page and the next web page it leads to.