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

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

上面是一个在线版本的矩阵上的dfs，我只能看到它是一个递归，为什么它是一个dfs？

来源

2016-03-02 KKKK

你为什么认为这不是DFS？换句话说，你认为哪种调用会首先发生 - 'dfsHelper（matrix，0，col）'或'dfsHelper（matrix，1,0）'？ –

我看到这是一个递归的例子。它不是搜索任何东西，因为它实际上并不做任何事情，但是递归是一个堆栈（确切地说调用堆栈），所以本质上就是深度优先。 – Andreas

噢，好吧，称之为[深度优先*遍历*]（https://en.wikipedia.org/wiki/Depth-first_traversal），那么如果这就是你所挂上的所有东西（维基百科页甚至是重定向到“深度优先搜索”）。你没有特别搜寻任何东西并不重要。 –

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

您发布的算法首先查看当前元素，然后递归调用自己的右侧和下侧子元素。该算法将在回溯到在下分支（i + 1，j）上运行之前充分探索正确的分支（在这种情况下，i，j + 1）。

如果你还在困惑DFS我先试试阅读Depth-First Search Wikipedia page，以获得更好的理解的算法是怎么一回事

来源

2016-03-02 17:58:24

j + 1是对的，i + 1是否下降？左边和右边是什么？ – KKKK

左右只是一个类似于使用二叉树的结构，对不起，如果这是令人困惑的，我会相应地编辑答案。但主要想法是，它完全沿着子分支走，无论它们被称为什么，在移动到下一分支 –

之前，所以如果我切换访问顺序和权利，它仍然是dfs，对不对？这次只是先冲下去。 – KKKK

-3

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

来源

2016-03-02 17:56:28 Prashant

您的第一行与您的其余三行矛盾 – FallAndLearn

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

来源

2016-03-02 17:58:23 FallAndLearn

您至少应该提及您从维基百科IMO采纳了此代码。 – nbro

完成。感谢提及。我忘了。 – FallAndLearn

请问如果在3x3矩阵看（例如），当它帮助：

00 01 02 10 11 12 20 21 22

你考虑：

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

来源

2016-03-02 18:07:10

深度优先搜索（DFS）和宽度优先搜索（BFS）是遍历图的两种不同样式。深度优先遍历子节点的单一路径，直到它到达特定分支或路径的最终节点。广度优先遍历从根节点开始检查一定深度的所有节点，然后遍历更深的图。

考虑具有00为根节点的例子：

深度优先遍历顺序：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，这是一个实现细节。

来源

2016-03-02 23:52:57 Travis

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

回答

相关问题