深度优先搜索总结

发表于 | | 阅读次数:

深度优先搜索(DFS)和广度优先搜索(BFS)都是一种对可能解答路径的枚举方式，深度优先搜索每次都从一个方向一直搜索到最终状态，然后进行回溯尝试枚举其他到达最终状态的路径。回溯的过程需要存储回溯点当前的状态，递归方法可以很好的完成这个任务，在递归方法之前设置状态信息，在递归后将状态信息设置回原值。如果设计递归方法是关键，递归方法对应着深度优先搜索的策略。本文尝试从几个例子尝试探索使用深度优先搜索方法的一般设计方法。

二维矩阵两点之间的路径遍历

一个典型的问题是迷宫问题，给出一个迷宫矩阵，0代表可以走的位置，1代表墙的位置，给出起始和出口位置的坐标，求出最小步数走出迷宫的路径，并且打印出这个路径。
解决这个问题的基本想法是枚举所有的从起始位置到出口位置的路径，并记录最短的那条路径，那么应该怎么样才可以全面不漏的列举所有的路径呢？我们从一个坐标点(x,y)出发，那么经过一步可以走的方向有上下左右四个方向，也就是（x-1,y）,(x+1,y),(x,y-1),(x,y+1)。计算了下一步的位置，我们需要判断，新的位置是否在矩阵内，是否是墙，是否是出口节点，如果不是上面以上特殊节点，我们就可以把新的节点作为基地继续上面的搜索过程。
很显然，以上的搜索过程可以用递归写出来，其中定义递归转移的状态是当前的的坐标，出口为下一个位置为出口位置，对于在矩阵内的不是墙，不是出口节点的搜索方法是朝4个方向进行探索。
除了输入信息：矩阵行列数，迷宫矩阵，起始坐标，输出信息：最小步数，最小步数路径，我们还需要一些辅助容器，为了方便我们对下一个位置的计算，我们定义一个4*2的二维数组，可以使用循环的方式对下一个位置进行计算，如向上可以使用（-1,0）加上原来的（x,y）进行计算。总的来说，我们需要的信息如下,可以通过声明全局变量的方式进行声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//输入值定义为全局变量
   public static int maze[][];
   //行，列
   public static int xlen, ylen;
   public static Position start,end;
   //辅助全局常量
   //上下，左右
   public static final int directions[][]={{-1,0},{1,0},{0,-1},{0,1}};
   //结果容器
   //用于存储最优的路径
   public static Stack<Position> optimalStack=null;
   //设置为最大值
   public static int optimalStep=Integer.MAX_VALUE;

定义好需要的信息，我们就可以设计算法获取结果，如何进行计算呢，其基本思路是下面这样

1
2
3
4
5
6
7
输入行列数
输入矩阵
输入起始位置和出口位置
将初始位置作为初始点进行搜索并将最优结果存储到结果容器中
输出最优的结果

那么如何”将初始位置作为初始点进行搜索并将最优结果存储到结果容器中”,这个是算法核心，因为求的是最优的结果，所以我们不能直接在optimalStep和optimalStack进行存储，需要在算法计算的时候为它们声明一个副本，然后在到达出口节点的时候将副本step与optimalStep比较，如果step小于optimalStep，那么应该将optimalStep变成step，并且用optimalStack记录当前的stack路径。
按照上面的思路，我们的递归方法的参数应该是（x,y,step,stack），即当前的坐标，当前已走的步数，当前的路径坐标栈。因为结果会在全局变量中更新，所以不需要返回值，按此思路，设计算法如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
描述：深度搜索过程
输入：当前的坐标(x,y),当前已走的步数，当前的路径栈
输出：结果在全局变量中更新
对于4个方向选取一个当前方向，做如下循环
	计算在从当前坐标走向当前方向的的新坐标(nx,ny)
	如果(nx,ny)超出当前矩阵的范围，则尝试下一个方向
	如果(nx,ny)是墙，则尝试下一个方向
	如果(nx,ny)是出口坐标，做如下动作
		将当前步数step+1，并将出口节点存储到路径stack中
		如果当前step<optimalStep，则optimalStep=step,optimalStack=stack
		将步数step-1,弹出出口位置，为下一次探索做准备
	如果不是以上三种情况，则执行如下动作
		将当前步数step+1,并且将(nx,ny)存储到stack中，并将(nx,ny)置为墙
		以（nx,ny,step,stack）为新的状态做搜索
		将步数回溯置为step-1,并且将(nx,ny)弹栈，将(nx,ny)置为非墙

以上即为深度搜索的算法，可见深度优先搜索是依赖于递归进行的，其中状态，特殊位置处理，搜索方法是三驾马车，其中状态的设计是根本。使用栈存储变量的路径是十分有效的方法，在递归方法上的路径存储基本上都是使用栈来进行，在递归回来的时候可以使用弹栈的方式继续进行搜索。其中看在递归的前后还将当前位置设置为墙，为的是方式新的状态返回到当前状态，递归返回后，我要将其设置回来。
每个状态都是递归计算的，这意味着每个状态的计算都是可以重复的，一样的，不一样之处应该在特殊位置进行处理，通常剪枝和出口都在特殊位置状态进行处理。
如此，我们便可以轻松写出深度搜索的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void dfs(int x,int y,Stack<Position> stack, int step){
      //从当前的节点网四个方向试探
      for(int i=0;i<4;i++){
          //获取下一个位置的坐标进行判断
          int nx=x+directions[i][0];
          int ny=y+directions[i][1];
          //超过迷宫范围
          if(nx<1||nx>xlen||ny<1||ny>ylen)
              continue;
          //新节点位置为墙
          if(maze[nx][ny]==1)
              continue;
          if(nx==end.x&&ny==end.y){
              //到达节点目标位置
              //如果当前步数小于最优步数，则更新最优步数为当前步数
              step++;
              stack.push(new Position(nx,ny));
              if(step<optimalStep){
                  optimalStack =(Stack<Position>)stack.clone();
                  optimalStep=step;
              }
              step--;
              stack.pop();
              return;
          }
          //如果不是最终节点的处理方式,可以跳到步子上，从新的节点上张望
          //站到下一个节点上（步数加一，压栈），并在新的节点上做深度遍历
          step++;
          stack.push(new Position(nx,ny));
          maze[nx][ny]=1;
          dfs(nx,ny,stack,step);
          step--;
          stack.pop();
          maze[nx][ny]=0;
      }
  }

在main函数中，我们就可以直接调用dfs(start.x,start.y,0,new Stack())后获取最优的结果。

二维矩阵连通区域计算

再来一个二维矩阵的深度优先搜索例子：给出一个矩阵，其中*代表空，@代表油田，一块油田的上下左右和对角相邻位置视为连通，连通的油田是一块区域，给出一个这样的矩阵，计算出连通区域的个数。
明确我们的目的是求出所有的连通区域的个数，基本想法是遍历所有的矩阵点，对于所有的油田点进行深度搜索，目的是将与当前油田点标记为已访问状态；而对于已访问的矩阵点或者空点不做处理。
我们的输入变量有矩阵行列，矩阵，输出变量是连通区域数，我们还需要辅助变量方向数组和标记数组，其中标记数组用来标记一个节点是否已经被访问到了。

1
2
3
4
5
6
7
8
9
10
11
12
//输入变量
private static char maze[][];
private static int row,col;
//辅助变量
//标志是否已经归入某个区域
private static boolean mark[][];
//分别是左上，上，右上，左，右，左下，下，右下
private static final int directions[][]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
//结果变量
private static int ans;

递归方法的设计，转移状态应该是当前的油田节点的坐标(x,y)，计算新的节点(nx,ny)有三个特殊状态:出界，空点，已访问的点，这三种状态应该直接跳过，进行下一个方向的尝试，处理以上三个特殊状态，那么就剩下未访问的相邻油田，应该设置新的油田节点为已访问状态，并且以(nx,ny)为新基点进行递归探寻。其核心思想如下

1
2
3
4
5
6
7
8
9
10
描述：标记和一个油田节点在同一连通区域的所有油田点
输入：当前油田点的坐标位置
输出：标记即可，标记完后结果数加一
对于8个方向计算新的下一个节点，做如下操作
	新的节点为(nx,ny)
	如果新的节点不再矩阵内，尝试下一个方向
	如果新的节点是空或者已被访问，尝试下一个方向
	不是以上三种情况，做如下操作
		标记（nx,ny）为已访问状态
		以(nx,ny)为基础状态递归调用

根据以上，我们写出java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void dfs(int x,int y){
    for(int i=0;i<8;i++){
        int nx=x+directions[i][0];
        int ny=y+directions[i][1];
        if(nx<1||ny<1||nx>row||ny>col)
            continue;
        if(maze[nx][ny]=='*')
            continue;
        if(mark[nx][ny]==true)
            continue;
        //设置相邻位置为已连通状态
        mark[nx][ny]=true;
        dfs(nx,ny);
    }
}

二叉树的最长路径

说完了二维矩阵的深度优先遍历，下面我们举个二叉树的深度优先遍历的应用，即给出一个二叉树，打印出最长的从根到叶子节点的路径。
如果仅仅是求最长的路径是多少，我们使用层次遍历即可，也就是对应于广度优先遍历，而如果要把路径求出来，需要深度优先遍历所有的路径，记录最长的那一条。
我们的输入是一个树根，需要辅助的变量有临时的路径栈和临时路径长，输出是最长的路径和路径长，临时路径栈和临时路径长可以作为方法参数传递，所以我们只需要定义全局的输出信息。

1
2
3
//输出信息
   public static Stack<TreeNode> longestTrace;
   public static long longestLength=0;

深度优先递归的状态是当前的节点，还有作为参数传递的临时路径栈和临时路径长。特殊位置点有两个，一是如果当前节点是null，则直接返回，二是如果当前节点是叶子节点，则应该比较当前的路径长度和最长的路径长度，如果当前的路径长度更长，则应该更新最长的路径长度和路径栈。
其他情况，递归遍历左子树和右子树。其实现过程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 public static void findLongestTrace(TreeNode root,long length,Stack<TreeNode> trace){
      if(root==null)
          return;
      if(isLeaf(root)){
          length++;
          trace.push(root);
          if(length>longestLength){
              longestTrace=(Stack<TreeNode>) trace.clone();
              longestLength=length;
          }
          length--;
          trace.pop();
      }
      //非叶子节点
//左子树不空
      if(root.left!=null){
          length++;
          trace.push(root);
          findLongestTrace(root.left,length,trace);
          length--;
          trace.pop();
      }
//右子树不空
      if(root.right!=null){
          length++;
          trace.push(root);
          findLongestTrace(root.right,length,trace);
          length--;
          trace.pop();
      }
  }

隐式深度优先搜索-素数环

有的问题可以通过优先搜索的方式解决，但是状态的定义并不像上面二维数组，树啊的那么容易定义，一个典型的例子就是素数环问题，给你一个数，比如6，让你将1-6所有能组成素数环的排列全部列出，素数环排列必须以1开始。所谓素数环，指的是任意相邻的数和都为素数，最后一个数和第一个数和也为素数。
我们的输入只有一个数，但是却隐含了一个数组，解决这个问题的基本想法是遍历所有的以1开始的所有排列，但是怎么遍历，肯定不能用多个循环，我们可以定义状态为当前放入的位置index,以6为例，我们尝试从放入6个位置的数，每个数从2-6中选取，如果一个状态不符合，可以立即进行回退尝试下一个数字，如果符合，则可以尝试下一个位置，直至到达容量。
为了完成这个任务，我们需要对6个数字进行标记是否处于已选入状态，如果是，则不应该再次选入。所以我们需要以下变量的支持。

1
2
3
4
5
6
7
8
9
10
11
//输入变量
    private static int n;
    //辅助变量
    //标记变量是否被访问到过
    private static boolean[] flag;
    //结果容器
    private static int caseNum;
    //代替栈
    private static int[] ans;

我们的状态是当前已经放置的位置index，刚开始我们会将1放入，并且标记1为已选中状态。对于一个已放入状态的index，我们需要检查比较index和index-1位置的和是否为素数，这是每一个index都需要做的事情。对于特殊位置index==n,意味着位置已经放完，应该检查index位置和1位置的值和是否为素数，如果是，则成功查找到一个，将其放入到结果容器中，然后返回。搜索的过程是查找2-n中未选中的数，尝试将其放入index+1位置，并递归调用index+1位置。在此之前应该设置选中的数为已选中状态，返回的时候将其设置为未选中状态。整个思路如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void dfs(int index){
    if(index>1){
        //开始检查后两个和是否为质数,不是的话直接返回
        if(!prime.contains(ans[index]+ans[index-1]))
            return;
    }
    if(index==n){
        //已经放入最后一个数，检查第一个数和最后一个数的和是否仍为质数
        if(prime.contains(ans[index]+ans[1])){
            caseNum++;
            System.out.println("Case "+caseNum);
            for(int i=1;i<=n;i++){
                System.out.print(ans[i]+" ");
            }
            System.out.println();
        }
        return;
    }
    //非出口节点
    for(int i=2;i<=n;i++) {
       if(flag[i]==false){
           //i可以尝试放入结果中
           ans[index+1]=i;
           //将i位置的值设置为已用
           flag[i]=true;
           dfs(index+1);
           //递归回来设置i为可以用的状态
           flag[i]=false;
       }
    }
}

这种隐式的深度优先递归的放入位置比较难想，这里一个数就相当于一个尝试的点，需要在递归的内部进行循环遍历，这样就变相的实现了多重循环的实现。

声明

本文首发表于我的博客,欢迎关注！已委托维权骑士为本站的文章进行维权，转载须注明文章出处，作者保留文章所有权。

坚持原创技术分享，您的支持将鼓励我继续创作！