浅谈深度优先搜索

——Summary of April(1)

​ 简单谈一下DFS(Depth First Search)，深度优先搜索。

​ DFS是一种搜索方法，对于解决算法题是一种很直接”暴力“的方法。根据我的理解，DFS会将所有的方法都枚举出来，然后从中找出符合条件的方法。如果列出的方法不满足条件，就会回溯到上一个选择节点，做另一个选择。就像走迷宫一样，如果你要从迷宫走出去，你就要找到那条正确的路，你要决定你朝哪一个方向走。

​ DFS方法就是在走迷宫的时候，从起点出发，把每一条路都走一遍，当走的那一条走不出去时（限制条件），他就会折回来，走另一条路，直到走出去了（结束条件）之后才停下来。

​ 假设你从起点出发，到了A，A下面有B、C、D三个方向，同时，B、C、D下还有其他的路，在只有一条路能走出去的情况下。DFS会从起点开始，一直往下走，并在走过的路上做一个标记。

​ 假设没有走过的是0，走过后是1。一开始，所有都是0，从起点开始走：

​ A–>B–>E(出不去），然后回到B，将B和E的标志改为1。因为B下面还有一条路F没有走过，所有F还是0，于是走另一条路F，当它发现仍然出不去时，再次回到B，将F的标志也改成1。

​ 此时发现 B下面的路已经走完了，所以得出从B走不出去的结论，然后回到上一级，也就是A。从A开始再次往下走，B已经走过置1，所以从C开始走，重复之前走B那一条路线的过程。直到最后找到出口，结束搜索。

举例：

题目来自力扣，岛屿个数问题，力扣连接：岛屿个数

题目：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例1：

输入:
11110
11010
11000
00000
输出：1

示例2：

输入:
11000
11000
00100
00011
输出:3
解释：没做岛屿只能由水平和/或竖直方向上相邻的陆地组成

​ 我们简单分析一下，给定这样的一个二维数组，我们要做的就是将所以岛屿找出来，即找出所以相连的1，也就是1的上下左右都是1的情况种数。于是我们可以得到一个初始，从第一个元素开始找，找到所有

符合条件的情况。

​ 我们从第一个数开始遍历，一个岛屿是所有相连的1组成的，假设第一个是1，从第一个开始，往上下左右四个方向找，遇到0的时候就停下来，如果还是1，就从那个1开始再找。

​ 你可能已经发现，这样会有很多重复的情况，而这会导致结果的偏差或者是程序执行的次数更多，更复杂。我们把1看做通过，0看做禁止。查找到的1，我们都让它变成0。直到最后四个方向都是0停止后，就找到了一个完整的岛。

代码如下：

public class NumberOfIsland{
    public int numIslands(char[][] grid){
        int count=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[i].length;j++){
                if(grid[i][j]=='1'){
                    Search(grid,i,j);
                    //每查找完成一次就是一个岛
                    count++;
                }
            }
        }
        return count;
    }
    public void Search(char[][] list,int i,int j){
        //保证在网格内
        if(i<0||i>list.length||j<0||j>list[i].length){
            return ;
        }
        //如果不是1就停止
        if(list[i][j]!='1'){
            return ;
        }
        //置0
        list[i][j]='0';
        Search(list, i+1, j);
        Search(list, i-1, j);
        Search(list, i, j+1);
        Search(list, i, j-1);
    }
}

​ 我们通过将已经查找过的1置0的方式，来减少了查找的次数，从而减少了运行的时间，在使用DFS时也要注意重复和循环，减少不必要的重复，同时小心陷入循环而导致程序一直运行下去。