Дерева і графи

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

Miriam Antona

Software engineer

Дерева — визначення

Зображення дерева з вузлами.

  • Вузлові структури даних
  • Кожен вузол може мати посилання на кілька вузлів.
Структури даних і алгоритми в Python

Дерева — терміни

Зображення дерева з вузлами. Кореневий вузол позначено жовтим.

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

Дерева — терміни

Зображення дерева з вузлами. Кореневий вузол позначено жовтим. Батьківський вузол позначено помаранчевим.

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

Дерева — терміни

Зображення дерева з вузлами. Кореневий вузол позначено жовтим. Батьківський вузол позначено помаранчевим, а його нащадки — зеленим.

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

Дерева — терміни

Зображення дерева з вузлами.

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

Дерева — терміни

Зображення дерева з вузлами на різних рівнях.

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

Дерева — бінарне дерево

Схематичне зображення бінарного дерева.

  • Кожен вузол має:
    • нуль нащадків
    • одного нащадка
    • двох нащадків
Структури даних і алгоритми в Python

Дерева — реалізація бінарного дерева

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

Зображення дерева з вузлами.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Структури даних і алгоритми в Python

Дерева — реальні застосування

  • Зберігання ієрархічних зв'язків
    • Файлова система комп'ютера
    • Структура документа HTML

  • Шахи: можливі ходи суперника

  • Алгоритми пошуку й сортування

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

Графи

Зображення графа з вузлами.

  • Набір:
    • вузлів/вершин
    • зв'язків/ребер
  • Дерева — це різновид графів
Структури даних і алгоритми в Python

Графи — типи

  • Орієнтовані графи:
    • є певний напрямок

Зображення орієнтованого графа.

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

Графи — типи

  • Неорієнтовані графи:
    • ребра без напрямку
    • взаємний зв'язок

Зображення неорієнтованого графа.

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

Графи — типи

  • Зважені графи:
    • числові значення на ребрах
    • можуть бути орієнтованими або ні

Зображення неорієнтованого графа з назвами міст і відстанями між ними.

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

Графи vs. дерева

Дерева

  • Не можуть містити циклів
  • Усі вузли мають бути з'єднані

Зображення дерева з вузлами.

Графи

  • Можуть містити цикли
  • Можуть бути нез'єднані вузли

Зображення графа з вузлами.

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

Графи vs. дерева

Дерева

  • Не можуть містити циклів
  • Усі вузли мають бути з'єднані

Зображення дерева з вузлами.

Графи

  • Можуть містити цикли
  • Можуть бути нез'єднані вузли

Зображення графа з вузлами. Є вузол, не з'єднаний з іншими.

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

Графи — приклади з реального світу

  • Зв'язки користувачів у соціальних мережах
    • дружба
    • підписки
    • вподобання
    • тощо
  • Локації та відстані
    • оптимізація маршрутів
  • Графові бази даних
  • Алгоритми пошуку й сортування
Структури даних і алгоритми в Python

Графи — реалізація

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

Зображення орієнтованого графа.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}
Структури даних і алгоритми в Python

Давайте потренуємось!

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

Preparing Video For Download...