DFS介绍 – 玩算法

示例练习>>>

DFS（Depth-First-Search）是深度优先搜索，他的实现原理是沿着一个方向一直往下走，直到走不动为止，然后往回走，查看上一个位置还有没有其分支，如果有就走上一个位置的其他分支，如果没有就继续回退 …… 。有一种不撞南墙不回头的感觉，如下图所示。

DFS 的使用模板

DFS 可以使用递归或者栈来实现，但一般情况下，使用递归更容易理解。DFS 的使用大致也可以分 3 类，就是树，图和矩阵，这里的树并不一定是真正的树，也有可能是我们假象的，比如排列组合的选择我们就可以把它想象成为一棵树，还有在回溯算法中很多题我们都可以把它想象成为一棵树，来分别看下他们的实现过程以及大致使用模板。

1，树的DFS使用模板

对于树来说他的 dfs 遍历比较简单，像前面讲的二叉树的前序遍历，中序遍历以及后序遍历的递归写法其实都是 DFS 。他就是先沿着一个方向往下走，当走不动（到叶子节点）的时候然后再往回走，如下图所示。

他的使用模板如下所示。

public void dfsTree(Tree root) {
    if (root == null)
        return;
    // 访问当前节点，不一定放在这，也可以放到其他地方
    System.out.println(root.val);
    for (int i = 0; i < root.子节点个数; i++) {
        dfsTree(root.第i个子节点);
        // 如果需要回溯，这里要撤销选择
    }
}

2，图的DFS使用模板

如果是图，我们可以从图中挑一个位置来访问，访问图的时候需要标记哪些点被访问过，防止出现重复访问的情况，关于图的模板可以参考图的遍历。

3，矩阵的DFS使用模板

对于矩阵的访问我们可以把它看做是一棵 4 叉树的前序遍历，图就不在画了，具体可以参考矩阵的BFS使用模板，遍历方式可以参考下树的DFS使用模板，代码如下。

// 如果是矩阵，需要访问和他挨着的上下左右4个方向，(x,y)是当前位置的坐标。
public void dfsMatrix(int[][] matrix, boolean[][] visited, int x, int y) {
    // 首先不能越界。
    if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length)
        return;
    // 如果当前位置被访问过，就不要在重复访问，直接跳过。
    if (visited[x][y])
        return;
    visited[x][y] = true;// 先标记，表示当前位置被访问过。
    // 访问当前位置的上下左右4个方向，也可以像BFS中使用for循环来访问他的4个方向。
    dfsMatrix(matrix, visited, x - 1, y);//上
    dfsMatrix(matrix, visited, x + 1, y);//下
    dfsMatrix(matrix, visited, x, y - 1);//左
    dfsMatrix(matrix, visited, x, y + 1);//右
    // 递归之后还要往回走，如果需要回溯这个位置要还原，
    // 如果不需要回溯，下面这行代码就不要写。
    visited[x][y] = false;
}

BFS 和 DFS 以及我们后面要讲的并查集在解决连通区域问题上很多时候是可通用的，比如我们后面要讲的被围绕的区域，岛屿数量等，但是 BFS 还有一个更有用的用途就是求最短路径。所以这里我们可以做个总结：如果是求所有路径要优先考虑 DFS （有时候可以转化为回溯算法），如果是求最短路径或最短距离一般优先考虑 BFS ，如果是合并连通的区域， BFS 和 DFS 都可以。