深度优先算法
1. 概述
算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
2. 实现方法
- 首先将根节点放入stack中。
- 从stack中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜寻并回传结果。
否则将它某一个尚未检验过的直接子节点加入stack中。 - 重复步骤2。
- 如果不存在未检测过的直接子节点。
将上一级节点加入stack中。
重复步骤2。 - 重复步骤4。
- 若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
3. 复杂度
- 时间复杂度
$${\displaystyle O(b^{m})}$$
b是分支系数，m是图的最大深度 - 空间复杂度
$${\displaystyle O(bm)}$$
b是分支系数，m是图的最大深度
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 wind.kaisa@gmail.com
