简介

深度优先遍历，顾名思义对于树或者图中的某个节点，尽可能往一个方向深入搜索下去。具体而言，从某个节点v出发开始进行搜索，不断搜索直到该节点的所有边都被遍历完。对于很多树、图和矩阵地搜索问题，深度优先遍历是一个非常有效的解法。

深度优先遍历（DFS）是图论的经典算法，以树为例，DFS尽可能深的搜索每个树枝，一直搜索到最深的那一个为止。对节点v来说，先是访问其子节点v_1_1，然后访问子节点的子节点v_1_1_1，直到到达叶子节点v_1_1_1_1再返回叶子节点的上一层对其他节点继续同样的搜索。下图为DFS的搜索顺序示例图（采用graph_editor绘制）。

栈实现

显然，从DFS的原理来看，节点的添加顺序若以栈来维护（后进后出）节点的访问，那么可以写出如下的模板。

def dfs(node):
    visited, stack = set(), [node]

    while stack:
        node = stack.pop()
        visited.add(node)
        print(node.val)
        nodes = node.nexts
        stack.append(nodes)

递归实现

当然，我们更多的是使用递归的方法来实现深度优先遍历，其模板代码如下。

def dfs(node):
    if node is None:
        return
    print(node.val)
    for node in node.nexts:
        dfs(node)

练习题

由于使用到DFS的题实在过多，这里也只列举几个典型的作为示例。

• 79. 单词搜索

补充说明

面对“存在性检验”的搜索题，应当优先考虑深度优先遍历。