Skip to content
Advertisement

Depth first search in finding a path in matrix

My understanding about dfs is using stack (bfs using queue). However, if i want to traversal a matrix in dfs. How do I suppose to do that?

Suppose I have a matrix and I want to find a path start from top left to bottom right, and it can only move down and right.

 public void dfsHelper(int[][] matrix, int i, int j ){                
    if (i >= row || j >= col) return;
    if (i == row - 1 && j == col - 1) {
        return;
    }
    dfsHelper(matrix, min, i, j + 1);
    dfsHelper(matrix, min, i + 1, j);
  }
}

Above is an online version a dfs on a matrix, I can only see it as a recursion, why it is a dfs?

Advertisement

Answer

Depth First Search is an algorithm mainly used for tree or graph traversal. What makes an algorithm a Depth First Search is that it searches all the way down a branch before backtracking up.

The algorithm you posted first looks at the current element, then recursively calls itself on the right and down children. The algorithm will fully explore the right branch (in this case i,j+1) before backtracking up to run on the down branch (i + 1, j).

If you are still confused about DFS I would first try reading the Depth-First Search Wikipedia page to get a better understanding of what the algorithm is all about

Advertisement