C++ 更多的DFS深度优先搜索...

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

目录

DFS模版

剪枝

DFS的两种状态

使用全局变量存储

使用函数参数存储传递


众所周知,DFS是一种省督有限搜索,可以想象成一棵树根节点K开始递归到最深层的节点,通常用来枚举符合题目的所有可能情况或者个数。

DFS模版

void dfs(int pos){
    if(pos == n+1){
        for(int i=1; i<=n; i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1; i<=k; i++){
        a[pos] = i;
        dfs(pos + 1); 
    }
}

话说,这个代码和全排列有什么不同吗哈哈哈哈哈

剪枝

剪枝时DFS中一个非常常见的优化手段。简单来说,剪枝的手段可以避免没必要的枚举和边界数据,防止超时或者数组越界。减少比必要的运算,减少不必要的时间。

DFS的两种状态

甲酸元素之和的样例,效果一样,可以使用两种不同的状态文章来源地址https://www.toymoban.com/news/detail-648271.html

使用全局变量存储

int sum = 0;
void dfs(int k){
    if(找到答案){
        输出或统计sum
        return;
    }
    for(int i=1;i<=k;i++){ //语句可变
        //操作合法时
        sum = sum + a[i];
        dfs(k + 1); //继续递归后面的位置
        sum = sum - a[i]; 
    }
}

使用函数参数存储传递

void dfs(int k, int sum){
    if(找到答案){
        输出或统计sum
        return;
    }
    for(int i=1;i<=k;i++){ //语句可变
        //操作合法时
        dfs(k + 1, sum + a[i]); 
    }
}

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

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

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

相关文章

  • c++深度优先搜索DFS

    目录 介绍 实现过程 模板 例题详解 1.枚举排列 2.迷宫寻路 3.八皇后 剪枝与优化 作业 今天我们来学习一个极其重要的算法:深度优先搜索。 深度优先搜索,又叫DFS,是遍历图或者数的一种算法,本质就是递归。具体方法:先以一个节点为起点,向一个方向扩展,再以新的节

    2024年01月16日
    浏览(35)
  • 深度优先搜索(DFS)算法

    目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 深度优先搜索(DFS)算法的思想是从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。具体而言,DFS算法使用栈数据结构来实现,

    2024年02月05日
    浏览(39)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(43)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(54)
  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

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

    2024年02月03日
    浏览(44)
  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

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

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

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

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

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

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

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

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

    2024年02月07日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包