c语⾔dfs,DFS（深度优先搜索）
1. DFS简介
c语言搜题软件推荐
深度优先搜索算法(英语：Depth-First-Search，简称DFS)是⼀种⽤于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分⽀。当节点v的所在边都⼰被探寻过或者在搜寻时结点不满⾜条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进⾏直到所有节点都被访问为⽌。属于盲⽬搜索，最糟糕的情况算法时间复杂度为O(!n)，DFS搜索的过程访问可以称之为DFS序。
如图：
对于⼀颗这样的树，我们的DFS序可以为：abdefc(即时对于同⼀颗的树，其DFS序不⼀定唯⼀)，即访
问a之后访问a的⼦结点b，再在b的基础上依次访问它的⼦结点def，最后回退到a处访问c。
这与前⽂花⼤篇幅介绍的先序，中序，后续遍历如出⼀辙，唯⼀的不同就是这样的⼀棵树并不只存在有左右两个结点，它可以是多枝的。
⽽即时对于⼀颗深度为n的⼆树，在没有任何优化的情况下适⽤DFS去搜索访问数据，其算法的时间复杂度也⾼达O(2^n)，在数据较⼤的情况下DFS是⽆法满⾜程序的时间要求，这就会涉及到⼀个思路——剪枝，即通过现有的数据判断接下来的数据⽆法再满⾜解，直接将当前结点以后的所有数据舍弃，遍历不再访问，通过精⼼设计的剪纸可以使得DFS搜索的效果得到很⼤提升。
2. 模板：
对于⼀个标准的DFS模板⽽⾔，其包括了以下的内容：bool check(参数)
{
if(满⾜条件)
return true ;
return false;
}
void dfs(int step)
{
判断边界
{
相应操作
}
尝试每⼀种可能
{
满⾜check条件
标记
继续下⼀步dfs(step+1)
恢复初始状态(回溯的时候要⽤到)
}
}
3. 相关习题
三⾓形(注，其还涉及了⼀点动态规划的思维)：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。