Поиск в глубину (DFS)

Структуры данных и алгоритмы на Python

Miriam Antona

Software engineer

Обход дерева/графа

• Процесс обхода всех узлов
• Поиск в глубину (DFS)
• Поиск в ширину (BFS)

Поиск в глубину — бинарные деревья

• Симметричный (In-order)
• Прямой (Pre-order)
• Обратный (Post-order)

Симметричный обход (In-order)

• Порядок: Левый

Симметричный обход (In-order)

• Порядок: Левый -> Текущий

Симметричный обход (In-order)

• Порядок: Левый -> Текущий -> Правый

Симметричный обход (In-order)

• Порядок: Левый -> Текущий -> Правый

Симметричный обход (In-order)

• Порядок: Левый -> Текущий -> Правый

Симметричный обход (In-order)

• Порядок: Левый -> Текущий -> Правый

Симметричный обход (In-order)

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход

• Порядок: Левый -> Текущий -> Правый

Симметричный обход — реализация

• Порядок: Левый -> Текущий -> Правый

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$ -> количество рёбер

Давайте потренируемся!

Структуры данных и алгоритмы на Python