深度优先搜索（DFS）

Python 中的数据结构与算法

Miriam Antona

Software engineer

树/图遍历

• 访问所有节点的过程
• 深度优先搜索（DFS）
• 广度优先搜索（BFS）

深度优先搜索 - 二叉树

• 中序
• 先序
• 后序

中序遍历

• 顺序：左

中序遍历

• 顺序：左 -> 当前

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历

• 顺序：左 -> 当前 -> 右

中序遍历 - 实现

• 顺序：左 -> 当前 -> 右

def in_order(self, current_node):

  if current_node:

    self.in_order(current_node.left_child)

    print(current_node.data)

    self.in_order(current_node.right_child)


my_tree.in_order(my_tree.root)

10
20
22
65
68
70
75

• 复杂度：$O(n)$
  • $n$ -> 节点数

先序遍历

• 顺序：当前

先序遍历

• 顺序：当前 -> 左

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历

• 顺序：当前 -> 左 -> 右

先序遍历 - 实现

• 顺序：根 -> 左 -> 右

  def pre_order(self, current_node):
    if current_node:
      print(current_node.data)
      self.pre_order(current_node.left_child)
      self.pre_order(current_node.right_child)

my_tree.pre_order(my_tree.root)

65
20
10
22
70
68
75

• 复杂度：$O(n)$
  • $n$ -> 节点数

后序

• 顺序：左

后序

• 顺序：左 -> 右

后序

• 顺序：左 -> 右 -> 当前

• 复杂度：$O(n)$

  • $n$ -> 节点数

何时用中序、先序、后序

• 中序

  • 用于从 BST 获取升序节点值

• 先序

  • 复制树
  • 获取前缀表达式

• 后序

  • 删除二叉树
  • 获取后缀表达式

深度优先搜索 - 图

• 图可含环
  • 需记录已访问顶点
• 步骤：
  1. 从任意顶点开始
  2. 将当前顶点加入已访问列表
  3. 对当前顶点的每个相邻顶点
     • 若已访问 -> 忽略
     • 若未访问 -> 递归执行 DFS

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 图

深度优先搜索 - 实现

def dfs(visited_vertices, graph, current_vertex):
    if current_vertex not in visited_vertices:
        print(current_vertex)
        visited_vertices.add(current_vertex)
        for adjacent_vertex in graph[current_vertex]:
            dfs(visited_vertices, graph, adjacent_vertex)

• 复杂度：$O(V+E)$
  • $V$ -> 顶点数
  • $E$ -> 边数

Vamos praticar!

Python 中的数据结构与算法