第一周算法训练(dfs)(深度优先搜索算法)

这篇具有很好参考价值的文章主要介绍了第一周算法训练(dfs)(深度优先搜索算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.什么是dfs,以及算法的基础是什么?

dfs:深度优先搜索算法,是一种用于遍历或搜索树或图的算法.沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。简单来说就是一条路走到黑,直到没路了,或者找到结果才返回。

深度优先搜索算法的基础:递归与回溯

递归与回溯是相辅相成的,有递归就会有回溯,递归函数的下面部分就是回溯的过程以及回溯的逻辑

回溯是一种纯暴力搜索。

2.使用原因

虽然深度优先搜索算法的效率很低,但是有些问题只能通过dfs来解决,有些时候多重循环就照不出来结果

能够解决的问题有:

1.组合问题         

2.切割问题

3.子集问题

4.排列问题

5.棋盘问题

3.如何去理解深度优先搜索的回溯算法

回溯算法是一个很抽象的东西,但是所有的回溯算法都可以抽象成一个树状结构,可以将其抽象成一个n叉树问题。树的深度取决于要搜索问题的层数,树的宽度取决于每个节点处理集合的大小。

回溯法的模版:

void 函数名(参数)//回溯算法的参数一般比较多,要根据具体情况进行分析
{
    if(终止条件)
      {
         收集最后节点结果
         return  ;
      }
//单层搜索的逻辑:
    for(集合的元素)//遍历的是集合里的每一个元素,也可能是集合节点的子节点个数
      {
          处理节点
          递归函数
          回溯操作(撤销处理节点的操作)
      }
    return ;
}

基本上一般的回溯问题都可以通过这个模版的变形从而解决问题

4.例题以及AC代码(C语言)

1.第一题

第一周算法训练(dfs)(深度优先搜索算法),算法,深度优先

这是洛谷上的一道dfs的入门题,我们通过这题来了解一下dfs

#include <stdio.h>
int n,m,t,p,q;//n和m分别代表迷宫有多少行和列,t代表有多少个障碍物,p和q是障碍物的坐标
int sx,sy,fx,fy;//输入起始位置和终止位置坐标
int a[6][6];//棋盘数组
int b[6][6];//标记数组,若元素是1,则代表这个位置已经访问过了,不用再次访问
int next[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//要进行操作的集合,分别代表右,下,左,上的移动
int count=0;//统计共有多少种方法
void dfs(int x,int y)//进行回溯的函数
{
    int dx,dy;//代替x,y进行移动操作,这样回溯的时候不用回溯x和y,只需要回溯标记就好,更简洁
    if(x==fx&&y==fy)//终止条件,当x和y到达终止位置时,会将次数加一,并且终止递归
    {
        count++;
        return ;
    }
    for(int i=0;i<4;i++)//遍历移动集合,进行移动
    {
        dx=x+next[i][0];//移动后的行坐标
        dy=y+next[i][1];//移动后的列坐标
        if(dx<1||dx>n||dy<1||dy>m)//假如数组越界就可以直接跳过(即边界的判断条件)
        {
            continue;
        }
        if(b[dx][dy]==0&&a[dx][dy]==0)//这个位置没有被访问过
        {
            b[dx][dy]=1;//标记访问
            dfs(dx,dy);//继续递归
            b[dx][dy]=0;//回溯
        }
    }
    return ;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
    b[sx][sy]=1;//将其实位置标记为1,代表一开始就访问过了
    while(t--)
    {
        scanf("%d%d",&p,&q);
        b[p][q]=1;//将障碍物标记为1,相当于访问过这样一视同仁代码更加简洁
    }
    dfs(sx,sy);//调用递归函数
    printf("%d\n",count);
}

可以看到这个基础题的代码和上述模版十分相似,但是后续的难题就不能完全依靠模板了,那个只是起到一个辅助的思路,主要还是需要自己思考

2.第二题

第一周算法训练(dfs)(深度优先搜索算法),算法,深度优先

首先根据题意,我们可以知道只有附近八格内,只要连续就可以构成一个水坑,那么我们就可以想到终止条件就是假如附近八格内没有水了就可以直接结束了,而函数里的参数就是首个出现的水坑,我们要进行循环的集合就是水坑的附近八格,因此我们可以写出AC代码文章来源地址https://www.toymoban.com/news/detail-830322.html

#include <stdio.h>
int n,m;
char a[105][105];//定义一个棋盘数组
int b[105][105];//标记数组
int count=0;
void dfs(int x,int y)//递归函数
{
    if(a[x][y]=='.')//终止条件就是碰到  .
    { 
        return ;
    }
    int dx,dy;
    for(int i=-1; i<=1; i++)
    {
        for(int j=-1; j<=1; j++)
        {
            dx=x+i;
            dy=y+j;
            if(dx>=0&&dx<=n&&dy>=0&&dy<m&&a[dx][dy]=='W'&&b[dx][dy]==0)
            {
                b[dx][dy]=1;
                dfs(dx,dy);//此处无需回溯,因为需要进行标记
            }
        }
    }
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)
    {
        scanf("%s",a[i]);
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a[i][j]=='W'&&b[i][j]==0)
            {
                dfs(i,j);
                count+=1;
            }
        }
    }
    printf("%d\n",count);
    return 0;
}

到了这里,关于第一周算法训练(dfs)(深度优先搜索算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(51)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(67)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(51)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(49)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(78)
  • 如何实现一个简单的深度优先搜索(DFS)算法?

    前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发者,这里都将为你提供一

    2024年02月07日
    浏览(54)
  • 【Python搜索算法】深度优先搜索(DFS)算法原理详解与应用,示例+代码

    目录 1 基本原理 2 DFS算法流程 3 时间复杂度 4 空间复杂度 5 DFS算法应用案例: 5.1 解决路径查找问题  5.2 解决图的连通性问题 5.3  拓扑排序 5.4  在树结构中进行深度遍历 深度优先搜索(DFS)是一种重要的图遍历算法,用于探索图中的节点和边。 DFS 是一种递归或栈(堆栈)

    2024年02月06日
    浏览(61)
  • Python算法:深度优先搜索—DFS(模板及其样例)

    • 沿着一条路径一直搜索下去,在无法搜索时,回退到刚刚访问过的节点。 • 并且每个节点只能访问一次。 • 本质上是持续搜索,遍历了所有可能的情况,必然能得到解。 • 流程是一个树的形式,每次一条路走到黑。 • 目的主要是达到被搜索结构的叶结点直到最后一层

    2024年03月24日
    浏览(49)
  • DFS(深度优先搜索算法)入门保姆级超详解

    如题,本篇创作目的在于更精细化理解DFS的运作,篇幅不长,也只是作者的一家之言,只为提供一个对入门者的更精细的解释。 DFS,深度优先搜索算法,首先我们看中文,可以很清楚的理解到这个算法是指搜索操作中优先进行深度也就是纵向的数据筛查。 看搜索的基本思路

    2024年02月07日
    浏览(48)
  • 【C++算法】dfs深度优先搜索(上) ——【全面深度剖析+经典例题展示】

    💃🏼 本人简介:男 👶🏼 年龄:18 📕 ps:七八天没更新了欸,这几天刚搞完元宇宙,上午一直练🚗,下午背四级单词和刷题来着,还在忙一些学弟学妹录制视频和准备开学一些事,一直没空出时间来,等 20号练完车,也马上开学了QAQ。不过今天倒是空出来一些时间,恰好这

    2024年02月02日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包