深度与广度优先搜索

function dfs(root) {
  const stack = [];
  const marked = {};

  stack.push(root);
  marked[root] = true;

  while(stack.length) {
    let v = stack.pop();
    visit(v);

    for(let u = 0; u < adj[v].length; u++) {
      if (!marked[u]) {
        stack.push(u);
        marked[u] = true;
      }
    }
  }
}

const marked = {};

function dfs(root) {
  visit(root);

  marked[root] = true;

  for(let u = 0; u < adj[root].length; u++) {
    if (!marked[u]) {
      dfs(u);
    }
  }
}

/**
 * 迷宫 maze[][]
 * 起点 A[x1, y1] --> 终点 B[x2, y2]
*/
function solve(maze) {
  // 1. 除 A 意外的所有 0 都填充为 MAX_NUMBER
  for (let i = 0; i < maze.length; i++) {
    for (let j = 0; j < maze[0].length; j++) {
      if(maze[i][j] === 0 && ! (i === A[0] && j === A[1])) {
        maze[i][j] === Infinity;
      }
    }
  }

  // 2. DFS 的结果为，maze 的每格被填充为离终点最近的步数
  dfs(maze, A[0], A[1]);

  // 3. 判断是否抵达
  if (maze[B[0]][B[1]] < Infinity) {
    console.log('找到');
  } else {
    console.log('没找到');
  }
}

function dfs(maze, x, y) {
  // 1. 判断是否到达目的地
  if (x === B[0] && y === B[1]) {
    return;
  }

  // 2. 从四个方向进行尝试
  for (let d = 0; d < 4; d++) {
    let i = x + dx[d], j = (y + dy[d];

    // 3. 判断下一点的步数是否大于当前步数 + 1
    if (isSafe(maze, i, j) && maze[i][j] > maze[x][y] + 1) {
      // 4. 若大于，则更新最较小的值，并继续 DFS
      maze[i][j] = maze[x][y] + 1; 
      dfs(maze, i, j)
    }
  }

}

function bfs(root) {
  const queue = [];
  const marked = {};

  queue.push(root);
  marked[root] = true;

  while(queue.length) {
    let v = stack.shift();
    visit(v);

    for(let u = 0; u < adj[v].length; u++) {
      if (!marked[u]) {
        stack.push(u);
        marked[u] = true;
      }
    }
  }
}