DFS——深度优先搜索的一般格式

　　DFS是一种深度优先的搜索思想，运用递归完成搜索，本质上也算是穷举思想的一类，可以通过剪枝进行优化。

　　DFS的核心是回溯和递归，如果以迷宫为例，一般会指定走各个方向的顺序（例如先左再上再右再下）。从起点开始，进入DFS()，判断是否到达终点，再判断四个方向是否可走，如果有路，DFS会进入下一格，并且进行同样的判断，此处运用了递归。当四个方向都没路时，就会回溯到上一个位置，继续判断别的方向。

　　DFS用途十分广泛，例如在以二维数组表示的图中搜索路径，也可以用于别的方面，比如求全排列，此时将每个数字看做一个点，每个全排列相当于从某个点开始将其他点连起来。

　　DFS的一般格式：（一般将变化的状态设置为参数，例如坐标、全排列中已选取数字个数）

 public static void dfs()//参数用来表示状态

 {

     if(到达终点状态)  {

         ...//根据题意添加

         return;

     }

     if(越界或者是不合法状态)

         return;

     if(特殊状态)//剪枝

         return ;

     for(扩展方式)  {          //在迷宫中则为四个方向的扩展

         if(扩展方式后的状态可行)  {    //例如在迷宫中，该方向可行

             修改操作;//根据题意来添加

             标记；  //在迷宫中标记为已走过

             dfs（）；

             (还原标记)；  //状态回溯，将标记移除

             //是否还原标记根据题意

         }  

     }

 }

巴特西

DFS——深度优先搜索的一般格式

最新文章

热门文章