深度优先算法

  1. 1. 概述
  2. 2. 实现方法
  3. 3. 复杂度

深度优先算法

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是图的最大深度

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 wind.kaisa@gmail.com

文章标题:深度优先算法

本文作者:kaisawind

发布时间:2020-06-11, 02:06:12

最后更新:2020-07-21, 14:35:46

原始链接:https://kaisawind.gitee.io/2020/06/10/2020-06-11-dfs/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏