深度优先搜索

本篇文章分享深度优先搜索，对你有帮助的话记得收藏一下，看极客资料网收获更多编程知识

一、深度优先搜索算法概述

深度优先搜索（Depth-First Search，DFS）是图论和树结构遍历中最经典的算法之一。该算法采用纵向扩展策略，沿着一条路径尽可能深入地探索，直到无法继续前进时才回溯到上一个分支点。DFS与广度优先搜索（BFS）形成鲜明对比，后者采用横向扩展的遍历方式。

1. 核心思想

DFS的核心在于“不撞南墙不回头”的探索方式：

• 从起始节点出发，随机选择一条分支深入
• 对访问过的节点进行标记（避免重复访问）
• 当到达末端节点（叶子节点或无法继续的节点）时，回溯到最近的分支点
• 重复上述过程直到遍历完所有可达节点

2. 算法特性

• 空间复杂度：O(h)，h为树/图的最大深度
• 时间复杂度：O(V+E)，V为顶点数，E为边数
• 不完全性：在无限深度图中可能无法找到解
• 非最优性：找到的解路径不一定是最短路径

代码实现（c++）

深搜 (Depth-First-Search,dfs)

int n,m,i,j,s=0;
int a[111][111];//bool
//四方向
int xx[9]={0,-1,0,1};
int yy[9]={-1,0,1,0};
//八方向
//int xx[11]={-1,-1,-1,0,0,1,1,1};
//int yy[11]={-1,0,1,-1,1,-1,0,1};
void w(int x,int y){
  if(x==fx&&y==fy){//终止条件
    s++;
    return;
  }
  for(int i=0;i<4;i++){
    int nx=x+xx[i],ny=y+yy[i];
    if(a[nx][ny]==0&&nx<=n&&ny<=n&&nx>0&&ny>0){
      a[nx][ny]=2;//1
      w(nx,ny);
      a[nx][ny]=0;//回溯
    }
  }
}

洪水填充(大洪水)(Flood fill)

int n,m,i,j,s=0;
int a[111][111];//bool
//四方向
int xx[9]={0,-1,0,1};
int yy[9]={-1,0,1,0};
//八方向
//int xx[11]={-1,-1,-1,0,0,1,1,1};
//int yy[11]={-1,0,1,-1,1,-1,0,1};
void w(int x,int y){
  s++;
  //无终止条件
  for(int i=0;i<4;i++){
    int nx=x+xx[i],ny=y+yy[i];
    if(a[nx][ny]==0&&nx<=n&&ny<=n&&nx>0&&ny>0){
      a[nx][ny]=2;//1
      w(nx,ny);
      //不回溯
    }
  }
}

文章来源:https://www.cnblogs.com/huan9178/p/20028653
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！