DFS解决什么问题

DFS解决的是连通性的问题，即给定两一个起始点（或某种起始状态）和一个终点（或某种最终状态)，判断是否有一条路径能从起点连接到终点。很多情况下，连通的路径有很多条，只需要找出一条即可，DFS只关心路径存在与否，不在乎其长短。

算法思想

从起点出发，选择一个可选方向不断向前，直到无法继续为止。

举例说明

image.png假设有这样一个图，如何对图进行遍历
必须依赖栈（Stack），特点是后进先出（LIFO）。

第一步，把起始顶点压入栈，标记它为访问，输出到结果中。（栈表示接下来要访问的坐标）

第二步，寻找与 A 相连并且还没有被访问过的顶点，顶点 A 与 B、D、G 相连，而且它们都还没有被访问过，我们按照字母顺序处理，所以将 B 压入栈，标记它为访问过，并输出到结果中。

第三步，现在我们在顶点 B 上，重复上面的操作，由于 B 与 A、E、F 相连，如果按照字母顺序处理的话，A 应该是要被访问的，但是 A 已经被访问了，所以我们访问顶点 E，将 E 压入栈，标记它为访问过，并输出到结果中。

第四步，从 E 开始，E 与 B、G 相连，但是B刚刚被访问过了，所以下一个被访问的将是G，把G压入栈，标记它为访问过，并输出到结果中。

第五步，现在我们在顶点 G 的位置，由于与 G 相连的顶点都被访问过了，所以我们这里要做的就是简单地将 G 从栈里弹出，表示我们从 G 这里已经无法继续走下去了，看看能不能从前一个路口找到出路。

这样继续直到到达终点。

先选一条路走到底之后再回溯

leetcode 490

给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。

  1. 输入 1: 迷宫由以下二维数组表示
  3. 0 0 1 0 0
  4. 0 0 0 0 0
  5. 0 0 0 1 0
  6. 1 1 0 1 1
  7. 0 0 0 0 0
  9. 输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
  10. 输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
  • 算法通常会直接修改 maze 来表明访问过该点，但是工作中不推荐，因为直接修改会导致原始数据结构改变
  • 另一种使用一种额外的数据结构来表示，我们来使用同样大小的二维数组来表示
    1. var hasPath = function (maze, start, destination) {
    2.   const stack = []
    3.   //栈来记录接下来要访问的位置
    4.   const visited = new Array(maze.length)
    5.   for (let k = 0; k < maze.length; k++) {
    6.       visited[k] = [];
    7.       for (let j = 0; j < maze[0].length; j++) {
    8.           visited[k][j] = false;
    9.       }
    10.   }
    11.   //创建二维数组
    12.   const [x, y] = start
    13.   const xDirection = [0, 1, -1, 0]
    14.   const yDirection = [1, 0, 0, -1]
    15.   stack.push(start)
    16.   visited[x][y] = true
    17.   function isSafe(i, j) {
    18.       const t = maze[i] !== undefined && maze[i][j] !== undefined && maze[i][j] !== 1
    19.       return !!t
    20.   }
    21.     //isSafe 判断是不是墙壁
    22.   while (stack.length >= 1) {
    23.       const [x, y] = stack.pop()
    24.       if (x === destination[0] && y === destination[1]) {
    25.           return true
    26.       }
    27.       for (let d = 0; d < 4; d++) {
    28.           let i = x + xDirection[d]
    29.           let j = y + yDirection[d]
    30.           while (isSafe(i, j)) {
    31.               i += xDirection[d]
    32.               j += yDirection[d]
    33.               if (!isSafe(i,j)) {
    34.                   if (visited[i - xDirection[d]][j - yDirection[d]] === true) {
    35.                       break
    36.                   }
    37.                   stack.push([i - xDirection[d], j - yDirection[d]])
    38.                   visited[i - xDirection[d]][j - yDirection[d]] = true
    39.               }
    40.           }
    41.       }
    42.   }
    43.   return false
    44. };
    栈中弹出要访问的点称为起点，向四个方向探索，如果起点后探索的点不是墙壁，那么一直沿着这个方向前进，直到遇到墙壁，将这个方向的最后一个点压入栈，并标记为访问，如果这个点已经被访问过那么肯定已经被压入栈过，它的之后可能的路线也被走过或者将要走所以直接 break 即可，一直这样下去直到到达终点或者没有地方去了。

    stack 的作用

    stack 就是深度算法的核心，将接下来要访问的点按顺序（例如上下左右的顺序）压入栈，根据栈的特性总是弹出右这个方向，所以这个顺序下的算法总是往尽量右这个深度去搜索，并且先沿着一条路线走到不能走为止，然后，然后开始回溯（弹栈）考虑路线上的支路。