Деревья и графы

Структуры данных и алгоритмы на 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

Графы и деревья

Деревья

  • Не могут содержать циклы
  • Все узлы должны быть связаны

Изображение дерева с узлами.

Графы

  • Могут содержать циклы
  • Узлы могут быть несвязными

Изображение графа с узлами.

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

Графы и деревья

Деревья

  • Не могут содержать циклы
  • Все узлы должны быть связаны

Изображение дерева с узлами.

Графы

  • Могут содержать циклы
  • Узлы могут быть несвязными

Изображение графа с узлами. Один узел не связан с остальными.

Структуры данных и алгоритмы на 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...