深度优先搜索法

出处：按学科分类—自然科学总论 山东人民出版社《方法大辞典》第129页（563字）

当搜索总是沿着从父节点到子节点的方向不断进行，直到无路可走时，才返回，这样的搜索方式叫做深度优先搜索法。

如果从节点P有可能到达节点C，则P叫做C的一个父节点，而C叫做P的一个子节点。如图所示，深度优先搜索，除搜索失败(即搜索不到目标)而要求返回来搜索原先被搁置的其他节点之外，在每一级只检查一个节点。这种搜索方法体现了优先向深度发展的趋势，所以这种深度优先搜索法又称为纵向优先搜索法。

这里需要提醒注意的是，深度优先搜索是一个冒失而危险的方法。

设想有更复杂的、树形结构层次多得多的树，在这样的结构中进行深度优先搜索过程，很容易出现滑过F节点的层次，而在穷尽下面的树形结构中进行搜索，这会浪费很多时间。对于这种树结构此方法虽然容易实现，却得到了最坏的可能路径。

当对复杂、多层次的树形结构进行深度优先搜索时，如果在离初始状态相当远的一段距离内搜索不到目标，我们就希望沿原路返回，去试探其他一些路径，而不继续向前搜索，以致离初始状态太远。在这种情况下，人们常常给搜索树规定一个深度界限，或称最大深度。

在考察一个节点时，如果其深度等于深度界限，就可不再向深度搜索，而从原路返回，去探索其他路径。这样有时就可节约时间，尽快搜索到目标。目前这一方法是作为搜索法的基本方法之一而得到广泛应用。