深度优先算法 - Thu, Jun 11, 2020

深度优先算法

1. 概述

算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

2. 实现方法

1. 首先将根节点放入stack中。
2. 从stack中取出第一个节点，并检验它是否为目标。 如果找到目标，则结束搜寻并回传结果。 否则将它某一个尚未检验过的直接子节点加入stack中。
3. 重复步骤2。
4. 如果不存在未检测过的直接子节点。 将上一级节点加入stack中。 重复步骤2。
5. 重复步骤4。
6. 若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

3. 复杂度

• 时间复杂度 $${\displaystyle O(b^{m})}$$ b是分支系数，m是图的最大深度
• 空间复杂度 $${\displaystyle O(bm)}$$ b是分支系数，m是图的最大深度