遍历或搜索树或图——DFS(深度优先搜索)算法讲解C语言代码示例

2022-07-1716:16:45数据结构与算法Comments1,137 views字数 834阅读模式

1. DFS简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

深度优先搜索算法(英语:Depth-First-Search,简称DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n),DFS搜索的过程访问可以称之为DFS序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

如图:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

遍历或搜索树或图——DFS(深度优先搜索)算法讲解C语言代码示例文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

对于一颗这样的树,我们的DFS序可以为:abdefc(即时对于同一颗的树,其DFS序不一定唯一),即访问a之后访问a的子结点b,再在b的基础上依次访问它的子结点def,最后回退到a处访问c。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

这与前文花大篇幅介绍的先序,中序,后续遍历如出一辙,唯一的不同就是这样的一棵树并不只存在有左右两个结点,它可以是多枝的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

而即时对于一颗深度为n的二树,在没有任何优化的情况下适用DFS去搜索访问数据,其算法的时间复杂度也高达O(2^n),在数据较大的情况下DFS是无法满足程序的时间要求,这就会涉及到一个思路——剪枝,即通过现有的数据判断接下来的数据无法再满足解,直接将当前结点以后的所有数据舍弃,遍历不再访问,通过精心设计的剪纸可以使得DFS搜索的效果得到很大提升。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

2. 模板:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

对于一个标准的DFS模板而言,其包括了以下的内容:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

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

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25178.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25178.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定