在矩阵中寻找路径的深度优先搜索

Question

我对dfs的理解是使用栈（bfs使用队列）。但是，如果我想遍历 dfs 中的矩阵。我应该怎么做？

假设我有一个矩阵，我想找到一条从左上角到右下角的路径，并且只能向下和向右移动。

 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);
  }
}

上面是网络版的a dfs on a matrix，我只能看成递归，为什么是dfs？

Answer 1

DFS和BFS是图遍历算法，不用于遍历矩阵。图可以用邻接矩阵的形式表示，如果算法谈论使用 DFS 遍历邻接矩阵，它实际上意味着它正在为矩阵表示的图或树这样做。 Here 是 Java 中的示例。

Answer 2

DFS和BFS是你说的两种遍历图或矩阵的方法。

现在回答你的问题。您正在使用 recursive 函数（与 stack 内部执行的操作相同），DFS 只是在回溯之前越走越深，同时在任何循环的情况下维护访问的顶点数组.你的方法完全一样。

Recursive 实施 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实施

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)

伪代码来源维基百科DFS

Answer 3

深度优先搜索是一种主要用于树或图遍历的算法。使算法成为深度优先搜索的原因是它在回溯之前一直搜索分支。

您发布的算法首先查看当前元素，然后在右侧和下方的子元素上递归调用自身。该算法将在向下分支 (i + 1, j) 回溯到运行之前充分探索正确的分支（在本例中为 i,j+1）。

如果您仍然对 DFS 感到困惑，我会先尝试阅读 Depth-First Search Wikipedia page 以更好地理解该算法的全部内容

Answer 4

以小型 (3x3) 矩阵为例可能更容易理解：

  00 01 02
  10 11 12
  20 21 22

因为你从(0,0)开始，只能“右”和“下”走，所以在做dfs时，会出现下面的树行走：

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

Answer 5

深度优先搜索 (DFS) 和广度优先搜索 (BFS) 是两种不同的图形遍历方式。深度优先遍历子节点的单一路径，直到它到达特定分支或路径的最终节点。广度优先遍历通过检查从根节点开始的一定深度的所有节点，然后再更深入地遍历图形。

考虑这个例子，其中 00 是根节点：

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

深度优先遍历顺序：00,01,02,03,11,12,13,21,22,23

广度优先遍历顺序：00,01,11,21,02,12,22,03,13,23

您可以使用 iteration、recursion 或两者来实现 DFS 或 BFS 算法，唯一决定您是否使用 DFS 或 BFS 是您检查节点的顺序。DFS 算法由于实现简单而倾向于 recursion，但 recursion 不保证DFS 和 DFS 不保证 recursion，这是一个实现细节。

在矩阵中寻找路径的深度优先搜索

Depth first search in finding a path in matrix

java

algorithm

traversal

depth-first-search