遍历或搜索树或图 - DFS（深度优先搜索）算法说明 C 语言代码示例

1。 DFS简介

深度优先搜索算法（英文：Depth-First-Search，简称DFS）是一种遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的边已经被探索过或者搜索时该节点不满足条件时，搜索将返回到找到节点v的边的起始节点。重复整个过程，直到所有节点都被访问过。这是一种盲目搜索，最坏情况算法的时间复杂度是O(!n)。 DFS搜索的过程方法可以称为DFS顺序。

如图：

对于这样一棵树，我们的DFS顺序可以是：abdefc（即使是同一棵树，DFS顺序也不一定唯一），即访问a之后，再访问child a b 的节点，然后在 b 的基础上按顺序访问子节点 def，最后回落到 a 访问 c。

这和上一篇介绍的前序、中序、后续遍历一模一样。唯一的区别是这样的树不仅仅只有左右两个节点，它可以是多分支的。

即使对于深度为n的二叉树，如果在不进行优化的情况下使用DFS来搜索和访问数据，算法的时间复杂度也高达O(2^n)。在数据量大的情况下，DFS无法满足程序的时间要求，这就会隐含一个想法——剪枝，即从已有的数据判断下一个数据已经不能满足解了，直接把后面的所有数据都扔掉当前节点和遍历None多次访问，通过精心设计的剪纸可以大大提高DFS搜索的效率。

2。模板：

对于标准的DFS模板，包含以下内容：