原标题：DFS---深度优先搜索

原文来自：CSDN      原文链接：https://blog.csdn.net/qq_41280600/article/details/102869042

一、介绍

深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
——————————————————————————————————————————————————————

二、核心内容

• 访问过程: 每一个节点入栈，当无下一个节点访问时出栈。用一个vis【】数组记录那些节点已经访问过。

• 从根节点1开始访问，1节点入栈。

  

• 从1节点出发访问它能够访问的点，访问到2节点，2节点入栈。
  

• 从2节点出发继续往下访问。2访问3节点，3节点入栈。又从3出发，3访问4， 4访问5。

  

• 最后5节点没有访问的点，进行出栈。
  

• 然后回溯到4节点， 继续从4节点出发直到遍历完全部节点。
  

• 最后节点全部出栈，完成DFS。
  

• 基本模板:

  int check(参数) {    if(满足条件)        return 1;    return 0;} void dfs(int step) {
         判断边界 {
             相应操作       }
         尝试每一种可能 {
                满足check条件
                标记
                继续下一步dfs(step+1)
                恢复初始状态（回溯的时候要用到）       }}

三、全排列

四、n皇后

五、迷宫

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com