CODEWITHSUNDEEP
javaalgorithmtraversaldepth-first-search
KKKK
KKKK

Reputation: 347

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?

Upvotes: 1

Views: 7312

Answers (5)

David Soroko
David Soroko

Reputation: 9086

It may be easier to look a small (3x3) matrix as an example :

  00 01 02
  10 11 12
  20 21 22

Because you start at (0,0) and can step only "right" and "down" ,while doing dfs, the following tree walk appears:

         00
      /   | 
     01   10
     |    |  \
     02   11  20
          |    |
          12   22

Upvotes: 5

Travis
Travis

Reputation: 1

Depth-first search (DFS) and breadth-first search (BFS) are two different styles of traversing through graphs. Depth-first traverses down a singular path of children nodes until it reaches the final node of a particular branch or path. Breadth-first traverses by examining all nodes of a certain depth from the root node before traversing deeper through the graph.

Consider this example with 00 being the root node: 

      00
  /   |   \
 01   11   21
 |    |    |
 02   12   22
 |    |    |
 03   13   23

Depth-first traversal order: 00, 01, 02, 03, 11, 12, 13, 21, 22, 23

Breadth-first traversal order: 00, 01, 11, 21, 02, 12, 22, 03, 13, 23

You can use iteration, recursion, or both to implement a DFS or BFS algorithm, the only thing that determines whether you are using DFS or BFS is what order you are examining nodes in. DFS algorithms tend to lend themselves towards recursion due to the simplicity of the implementation, but recursion does not guarantee DFS and DFS does not guarantee recursion, that is an implementation detail.

Upvotes: 0

Gordon Allocman
Gordon Allocman

Reputation: 778

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

Upvotes: 1

FallAndLearn
FallAndLearn

Reputation: 4135

DFS and BFS are two methods of traversing a graph or matrix as you say.

Now coming onto your question. You are using a recursive function (Same thing that a stack internally does), DFS is nothing but traversing deeper and deeper before backtracking up while maintaining the visited vertex array in case of any cycles. Your method does exactly the same.

Recursive implementation of DFS

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

Iterative implementation

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop()
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

Pseudocode source is Wikipedia DFS

Upvotes: 1

Prashant
Prashant

Reputation: 5383

DFS and BFS are graph traversing algorithms and not used for traversing matrix. A graph can be represented in form of an Adjacency matrix and if an algorithm talks about traversing an adjacency matrix using DFS, it actually means that it is doing so for the graph or a tree that the matrix represents. Here is an example in Java.

Upvotes: -4

Related Questions