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

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

Miriam Antona

Software engineer

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

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

Пошук у глибину — бінарні дерева

• In-order
• Pre-order
• Post-order

Обхід in-order

• Порядок: Left

Обхід in-order

• Порядок: Left -> Current

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order

• Порядок: Left -> Current -> Right

Обхід in-order — реалізація

• Порядок: Left -> Current -> Right

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$ -> кількість вершин

Обхід pre-order

• Порядок: Current

Обхід pre-order

• Порядок: Current -> Left

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order

• Порядок: Current -> Left -> Right

Обхід pre-order — реалізація

• Порядок: Root -> Left -> Right

  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$ -> кількість вершин

Post-order

• Порядок: Left

Post-order

• Порядок: Left -> Right

Post-order

• Порядок: Left -> Right -> Current

• Складність: $O(n)$

  • $n$ -> кількість вершин

Коли використовувати in-order, pre-order і post-order

• in-order

  • використовують у BST, щоб отримати значення вершин у зростальному порядку

• pre-order

  • створення копій дерева
  • отримання префіксних виразів

• post-order

  • видалення бінарних дерев
  • отримання постфіксних виразів

Пошук у глибину — графи

• У графах можуть бути цикли
  • треба відстежувати відвідані вершини
• Кроки:
  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