浅谈dfs深度优先搜索

深度优先搜索（Depth First Search）是一种常见的暴力算法

此算法上限和下限较高，容易上手，适用情形多，学习性价比高

下限高于有固定的模板，且时间复杂度明显优于暴力枚举，容易拿到题目部分分

int  DFS (int  k)//DFS常见模板

{

    if    (到目的地(边界))

    {

           输出结果; 

    }

    else

    {

        for (int i = 1; i <= n;++i)

        {

            if  (满足条件)

            {

                保存边界;

                DFS(k+1);

                恢复第k步的状态; 

            } 

        }

    }

}

上限高于可优化性高，通过剪枝优化可以大幅度缩小数据搜索范围，以达到意料之外的结果

适用范围广，属于算法竞赛中的万金油算法

而同时dfs也拥有一些缺点

时间复杂度较高（最坏情况为O（n！））很难拿到高分

对比兄弟算法bfs广度优先搜索不适用于对问题最优解的的求解

……

所以我们要结合多方面因素，权衡利弊，在比赛中选取最优的方法，以获取更高的得分

巴特西

浅谈dfs深度优先搜索

最新文章

热门文章