Новости

ДЕРЕВЬЯ И ГРАФЫ: ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

Деревья: типы и методы обхода

Виды деревьев

Методы обхода деревьев

def in_order_traversal(root):
  if root:
    in_order_traversal(root.left)
    print(root.data, end=' ')
    in_order_traversal(root.right)

def pre_order_traversal(root):
  if root:
    print(root.data, end=' ')
    pre_order_traversal(root.left)
    pre_order_traversal(root.right)

def post_order_traversal(root):
  if root:
    post_order_traversal(root.left)
    post_order_traversal(root.right)
    print(root.data, end=' ')

from collections import deque

def level_order_traversal(root):
  if root is None:
    return

  queue = deque([root])
  while queue:
     node = queue.popleft()
     print(node.data, end=' ')
     if node.left:
       queue.append(node.left)
     if node.right:
       queue.append(node.right)

Расширенные концепции обхода

Практическое применение деревьев

Графы: представление и основные алгоритмы

Основные понятия

Представление графов

class Graph:
  def __init__(self, size):
    self.adj_matrix = [[0 for _ in range(size)] for _ in range(size)]

  def add_edge(self, start, end):
    self.adj_matrix[start][end] = 1
    self.adj_matrix[end][start] = 1 # Для неориентированного графа

  def remove_edge(self, start, end):
    self.adj_matrix[start][end] = 0
    self.adj_matrix[end][start] = 0 # Для неориентированного графа

# Пример использования
graph = Graph(3)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
print(graph.adj_matrix)

class Graph:
  def __init__(self, size):
    self.adj_list = [[] for _ in range(size)]

  def add_edge(self, start, end):
    self.adj_list[start].append(end)
    self.adj_list[end].append(start) # Для неориентированного графа

# Пример использования
graph = Graph(3)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
print(graph.adj_list)

Основные алгоритмы построения графов

def dfs(graph, start, visited=None):
  if visited is None:
    visited = set()
  visited.add(start)
  for neighbor in graph.adj_list[start]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)
  return visited

from collections import deque

def bfs(graph, start):
  visited = set()
  queue = deque([start])
  while queue:
    vertex = queue.popleft()
    if vertex not in visited:
      visited.add(vertex)
      queue.extend(set(graph.adj_list[vertex]) - visited)
  return visited

Практическое применение графов

• Социальные сети. Графовые структуры используются на платформах некоторых социальных сетей. Пользователи представлены в виде узлов, а связи, такие как дружба или профессиональное взаимодействие, — в виде ребер. Такое графическое представление не только упрощает визуальную сложность сетей, но и помогает пользователям легко ориентироваться в обширной сети связей на этих платформах.
• Маршрутизация в Интернете. Маршрутизаторы используют графовые алгоритмы, в том числе алгоритм Дейкстры, для поиска наиболее эффективных путей передачи пакетов данных по сети. Эти алгоритмы учитывают различные аспекты топологии сети, такие как пропускная способность канала, задержка и перегруженность, чтобы выполнять эффективную маршрутизацию пакетов. Такой оптимальный поиск путей обеспечивает своевременную доставку данных, сокращает задержки и повышает общую эффективность сети.
• Рекомендательные системы. Платформы электронных продаж и контента, такие как Amazon и Netflix, используют алгоритмы на основе графов в своих рекомендательных системах. Они связывают пользователей с товарами или контентом, соответствующими их предпочтениям, на основе индивидуального выбора пользователей. Эти алгоритмы анализируют обширные данные о пользователях, выявляют тенденции и дают соответствующие рекомендации, постоянно предлагая новые варианты.
• Карты Google. Графические алгоритмы используются для определения наиболее эффективных маршрутов между населенными пунктами, учитывая расстояние, трафик, перекрытие дорог и другие важные данные. Благодаря этим усовершенствованным алгоритмам карты Google предоставляют точные данные в режиме реального времени, гарантируя пользователям беспроблемную поездку.

Практические советы

Практические упражнения

• Создайте базовое двоичное дерево поиска с методами вставки и обхода по порядку.
• Вставьте числа 10, 5, 15, 2, 5, 13, 22, 1, 14, а затем выполните обход по порядку.

class Node:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None
class BinarySearchTree:
  def __init__(self):
    self.root = None

  def insert(self, value):
    new_node = Node(value)
    if self.root is None:
      self.root = new_node
      return
    current = self.root
    while True:
      if value < current.value:
        if current.left is None:
          current.left = new_node
          return
        current = current.left
      else:
        if current.right is None:
          current.right = new_node
          return
        current = current.right

  def in_order_traversal(self, node, result=[]):
    if node:
      self.in_order_traversal(node.left, result)
      result.append(node.value)
      self.in_order_traversal(node.right, result)
    return result

# Тест
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
  bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Вывод: [1, 2, 5, 5, 10, 13, 14, 15, 22]

• Создайте класс Graph с методами для добавления ребер и выполнения поиска в ширину.
• Добавьте ребра, соединяющие узлы 0, 1, 2, 3 и 4 нелинейным образом, и выполните поиск в ширину, начиная с узла 0.

from collections import defaultdict, deque

class Graph:
  def __init__(self):
    self.graph = defaultdict(list)

  def add_edge(self, u, v):
    self.graph[u].append(v)

  def bfs(self, start):
    visited = set()
    queue = deque([start])
    while queue:
      vertex = queue.popleft()
      if vertex not in visited:
        print(vertex, end=' ')
        visited.add(vertex)
        queue.extend(set(self.graph[vertex]) - visited)

# Тест
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
  g.add_edge(u, v)
g.bfs(0) # Вывод: 0 1 2 3 4

• Реализуйте поиск в глубину для графа, созданного в упражнении 2.
• Выполните поиск в глубину, начиная с узла 0.

def dfs(graph, start, visited=None):
  if visited is None:
    visited = set()
  visited.add(start)
  print(start, end=' ')
  for neighbor in graph.graph[start]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)

# Тест
dfs(g, 0) # Выход: 0 1 2 4 3

Резюме