Python|DFS（深度优先搜索）介绍

vlambda
2020-04-05

Python|DFS（深度优先搜索）介绍

问题描述

在众多算法中，时常会用到一种适用于大多数情况的方法，这就是遍历。遍历中的DFS（深度优先搜索）就是今天要介绍的。DFS有递归性结构中最重要的一些属性，一旦在某个节点启动了DFS，就能确保自己能在相关操作继续下去之前遍历完其他所有能达到的节点。

解决方案

任何递归函数都可以用迭代操作来写，一种做法是用栈来模拟调用栈。这种基于迭代操作的DFS是非常实用的，它既可以避免调用栈被塞满带来的问题，也能因此改善算法的某些属性，使其显得更为清晰一些。为了模拟递归遍历，只需要使用一个栈结构。

代码示例(迭代DFS) ：

def iter_dfs(G,s):
    S,Q = set(),[]   #访问集合和队列
    Q.append(s)      #我们计划访问s
    while Q:
        u = Q.pop() #使程序进展
        if u in S:continue #是否访问过？跳过
        S.add(u)
        Q.extend(G(u))
        yield u             #u就是我们要的

为了让这段遍历更实用，添加了一个yield语句，它能按照DFS的顺序来遍历目标结构中的节点。DFS按照“先序遍历的方式”对顶点进行访问，其核心是栈的使用，而且可以用递归实现。

END

实习主编 | 王楠岚

责编 | 刘仕豪

where2go 团队

温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！

vlambda博客
学习文章列表