javascript - DFS 矩阵的正确方法是什么？

Question

我做这道练习题是为了找出一个词是否存在于矩阵中，这让我意识到我并不完全理解 DFS。

在 Cracking the Coding Interview 中，DFS 的伪代码是:

void search(Node root) {
  if (root == null) return;
  visit(root);
  root.visited = true;
  for each (Node n in root.adjacent) {
    if (n.visited == false) {
      search(n);
    }
  }
}

对我来说，这看起来像这样的格式:

1. 目标
2. 标记
3. 循环
4. 如果邻居不满足条件，则提早保释
5. 递归

所以用这种格式，我写了函数dfs():

  function dfs(r, c, i) {    
    // goal
    if (i === word.length-1) return true;

    // mark
    board[r][c] = '#';

    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      // recursion
      var result = dfs(nr, nc, i+1);

      // un-mark
      board[r][c] = word[i];

      return result;
    }
  }

其次，我注意到大多数解决方案根本不使用 for 循环，而只是为每个邻居编写 4 次递归。考虑到这一点，我编写了 dfs2():

1. 目标
2. 如果当前节点不满足条件，则提前退出
3. 标记

4. 递归

   function dfs2(r, c, i) {    
   // goal
   if (i === word.length) return true;
   
   // bail early if current does not meet conditions
   if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;  // current is out of bounds
   if (board[r][c] === '#') return false;                                          // current already visited
   if (board[r][c] !== word[i]) return false;                                      // current does not meet goal
   
   // mark
   board[r][c] = '#';
   
   // recursion
   var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1);
   
   // un-mark
   board[r][c] = word[i];
   
   return result;
   }
   

这更简洁，但对我来说更难理解。第一个版本 dfs() 做了一个循环，并在递归之前尽早放弃了邻居，这对我来说更有意义。 “如果邻居不好，就不要去那里。”第二个版本没有循环，因此它会在当前节点上执行所有检查。

我注意到的第一件事是，在涉及网格的大多数问题中，解决方案都涉及递归后的“取消标记”。为什么是这样？这是否仅适用于“单词搜索问题”等特定情况，您可能希望将来以不同的路径重新访问该节点？

哪个是正确的，dfs() 或 dfs2()？

---

https://repl.it/MSCw/0以下是全部内容:

var dirs = [
  [0,1],  // r
  [1,0],  // d
  [0,-1], // u
  [-1,0], // l
];

var wsBoard = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
];

var exist = function(board, word, version) {
  for (var r = 0; r < board.length; r++) {
    for (var c = 0; c < board[0].length; c++) {
      if (board[r][c] === word[0])
        if (dfs(r, c, 0)) return true;
        // if (dfs2(r, c, 0)) return true;
    }
  }

  return false;

  function dfs(r, c, i) {
    console.log(`(${r},${c})\t${i}: ${word[i]}`);

    // goal
    if (i === word.length-1) return true;

    // mark
    board[r][c] = '#';

    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      console.log(board);

      // recursion
      var result = dfs(nr, nc, i+1);

      // un-mark
      board[r][c] = word[i];

      return result;
    }
  }

  function dfs2(r, c, i) {
    console.log(`(${r},${c})\t${i}: ${word[i]}`);

    // goal
    if (i === word.length) return true;

    // bail early if current does not meet conditions
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;  // current is out of bounds
    if (board[r][c] === '#') return false;                                          // current already visited
    if (board[r][c] !== word[i]) return false;                                      // current does not meet goal

    // mark
    board[r][c] = '#';

    console.log(board);

    // recursion
    var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1);

    // un-mark
    board[r][c] = word[i];

    return result;
  }
};

console.log(exist(wsBoard, 'ABCCED'));  // => true
console.log(exist(wsBoard, 'SEE'));     // => true
console.log(exist(wsBoard, 'ABCB'));    // => false

Answer 1

我相信尽管 dfs 和 dfs2 都基于相同的想法 dfs 有一个缺陷，它返回的结果是只探索第一条路!

看看这个例子，我试图在板中找到 FOO，很明显，它是第一列，但是你的实现返回 false

var dirs = [
  [0,1],  // r
  [1,0],  // d
  [0,-1], // u
  [-1,0], // l
];

var board = [
  ['F','O','X'],
  ['O',' ',' '],
  ['O',' ',' ']
];

var exist = function(word) {
  function dfs(r, c, i) {
    // mark
    board[r][c] = '#';

    // goal
    if (i === word.length-1) return true;

    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      // recursion
      var result = dfs(nr, nc, i+1);

      // un-mark
      board[r][c] = word[i];

      return result;
    }
  }
  for (var r = 0; r < board.length; r++) {
    for (var c = 0; c < board[0].length; c++) {
      if (board[r][c] === word[0]) {}
        if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

console.log(exist('FOO'))

问题是您的 for 循环将始终返回第一次递归的结果，要修复它，让我们将 result 移到循环之外，使其成为 false 并在找到有效路径后使其采用 true 的值。

var dirs = [
  [0,1],  // r
  [1,0],  // d
  [0,-1], // u
  [-1,0], // l
];

var board = [
  ['F','O','X'],
  ['O',' ',' '],
  ['O',' ',' ']
];

var exist = function(word) {
  function dfs(r, c, i) {
    // mark
    board[r][c] = '#';

    // goal
    if (i === word.length-1) return true;

    // assume that there's no valid path initially
    var result = false
    // loop and recurse each neighbor
    for (var d of dirs) {
      var nr = r + d[0];
      var nc = c + d[1];

      // bail early if neighbor does not meet conditions
      if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue;  // neighbor is out of bounds
      if (board[nr][nc] === '#') continue;                                            // neighbor already visited
      if (board[nr][nc] !== word[i+1]) continue;                                      // neighbor does not meet goal

      // recursion
      result = result || dfs(nr, nc, i+1);

    }

    // un-mark
    board[r][c] = word[i];
    
    return result;
  }
  for (var r = 0; r < board.length; r++) {
    for (var c = 0; c < board[0].length; c++) {
      if (board[r][c] === word[0]) {}
        if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

console.log(exist('FOO'))

如果我们查看 dfs2，唯一的区别是 for 循环是展开的，例如

var result = false;
for (var dir in dirs) {
   // ...
   result = result || dfs(nr, nc, i+1)
}
return result;

// becomes

var result = dfs2(...) || dfs2(...) || ... 

The first things that I noticed was that in most problems involving a grid, solutions involve "un-marking" after the recursion. Why is this?

在某些解决方案中，您实际上可能会改变您正在使用的对象，例如在另一个经典问题中，该问题是找到一个单词的所有排列，您可以通过递归地改变单词来解决它，在找到一个排列后下一次递归调用将使用不同的状态(这是不希望的)，此问题中的unmarking 概念被翻译成将单词转换为其先前状态的还原操作。

Which is correct, dfs() or dfs2()?

两者都是正确的(好吧，在 dfs 修复之后)，但是，dfs2 会递归到无效状态，例如越界单元格或不属于单词的单元格，就复杂性而言，这种额外的开销只是一个常数乘数，例如即使您想象从每个单元访问每个邻居，复杂度也是 O(4 * # rows * # columns)