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模板网!

原文地址:https://blog.csdn.net/GeekAlice/article/details/132276605

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包