llmdocsсправочник разработчика

Дерево и граф

Материал из llmdocs — справочник разработчика
Портал: Основы CS
Дерево и граф
Графмножество вершин и рёбер G = (V, E)
Деревосвязный граф без циклов, n вершин и n − 1 рёбер
Представлениясписок смежности, матрица смежности
Обходыпоиск в ширину (BFS), поиск в глубину (DFS)
Классические алгоритмыДейкстра, A*, топологическая сортировка, Крускал, Прим
Деревья в практикеBST, AVL, красно-чёрное, B-дерево, куча, префиксное дерево

Граф — математическая модель объектов (вершин, узлов) и связей между ними (рёбер); формально G = (V, E). Дерево — частный случай графа: связный граф без циклов, в котором между любыми двумя вершинами ровно один путь. Обе модели относятся к базовым структурам данных: графами описывают дороги, сети, социальные связи и зависимости пакетов, деревьями — файловые системы, HTML-документы, индексы баз данных и синтаксис программ.[1]

Графы

Виды

  • Ориентированный (рёбра-стрелки: «A зависит от B») и неориентированный («A дружит с B»).
  • Взвешенный — у рёбер есть стоимость: расстояние, задержка, цена.
  • Ациклический ориентированный граф (DAG) — нет направленных циклов. Это граф зависимостей пакетов, задач сборки, пайплайнов данных и история коммитов Git.[6]
  • Связный, двудольный, плотный и разреженный — в зависимости от структуры и числа рёбер.

Представление в памяти

Способ Память Есть ли ребро (u, v) Обход соседей
Список смежности O(V + E) O(степень u) O(степень u)
Матрица смежности O(V²) O(1) O(V)

Реальные графы обычно разреженные, поэтому стандартный выбор — список смежности, например словарь списков:

graph = {
    "app":    ["web", "db"],
    "web":    ["http"],
    "db":     ["driver"],
    "http":   [], "driver": [],
}

Обходы

Поиск в ширину (BFS) обходит вершины «слоями» с помощью очереди и находит кратчайший путь по числу рёбер. Поиск в глубину (DFS) идёт по одной ветке до конца с помощью стека или рекурсии; на нём основаны поиск циклов, компонент связности и топологическая сортировка. Оба работают за O(V + E).[2]

from collections import deque

def bfs(graph, start):
    seen, order, queue = {start}, [], deque([start])
    while queue:
        v = queue.popleft()
        order.append(v)
        for w in graph[v]:
            if w not in seen:
                seen.add(w)
                queue.append(w)
    return order

Классические алгоритмы

  • Алгоритм Дейкстры (1959) — кратчайшие пути во взвешенном графе с неотрицательными весами, O((V + E) log V) с кучей.[3] Его модификация A* использует эвристику и применяется в навигаторах и играх; Беллман — Форд допускает отрицательные веса.
  • Топологическая сортировка — линейный порядок вершин DAG, при котором каждая зависимость идёт раньше зависимого. Так пакетные менеджеры и системы сборки решают, что устанавливать или собирать первым; в Python есть готовый graphlib.TopologicalSorter.[4]
  • Минимальное остовное дерево (Крускал, Прим) — самый дешёвый способ соединить все вершины.
  • Максимальный поток, поиск сильно связных компонент, PageRank.

Для экспериментов в Python удобна библиотека NetworkX.[5]

Деревья

Дерево обычно корневое: одна вершина — корень, у остальных есть родитель; вершины без детей — листья. Глубина дерева определяет стоимость операций, поэтому многие виды деревьев следят за балансом.

  • Двоичное дерево поиска (BST): слева ключи меньше, справа больше; поиск за O(h), где h — высота. В худшем случае (вставка отсортированных ключей) дерево вырождается в список и h = n.
  • Сбалансированные деревья — AVL и красно-чёрные — поддерживают высоту O(log n). На них построены std::map в C++, TreeMap в Java, BTreeMap в Rust (на самом деле B-дерево).
  • B-дерево и B+-дерево — сильно ветвящиеся деревья, оптимизированные под чтение страницами с диска; основа индексов PostgreSQL, SQLite и файловых систем.
  • Куча (heap) — дерево, где родитель не больше детей; очередь с приоритетом за O(log n), хранится в массиве (heapq в Python).
  • Префиксное дерево (trie) — поиск по префиксу строки: автодополнение, маршрутизация URL и IP-адресов.
  • Синтаксические деревья (AST) — промежуточное представление программы в компиляторах и интерпретаторах; DOM — дерево HTML-документа.

В отличие от хеш-таблицы, упорядоченные деревья позволяют обходить ключи по порядку и искать диапазоны («все заказы с 1 по 15 ноября»), ценой O(log n) вместо O(1) на операцию.

Где встречается

  • файловая система — дерево каталогов (жёсткие и символические ссылки делают её графом);
  • DNS — дерево доменных зон;
  • маршрутизация в сетях — поиск кратчайших путей (OSPF использует Дейкстру);
  • системы сборки, CI/CD-пайплайны и оркестраторы задач — DAG;
  • графовые базы данных и графы знаний, рекомендательные системы;
  • сборщики мусора обходят граф объектов, начиная с корней (см. Сборка мусора).

См. также

Источники

  1. Cormen et al. — Introduction to Algorithms, 4th ed., parts III and VI (MIT Press)
  2. Sedgewick, Wayne — Algorithms, 4th ed., ch. 3–4
  3. Dijkstra — A note on two problems in connexion with graphs (1959)
  4. Python — graphlib.TopologicalSorter
  5. NetworkX documentation
  6. Git — Git Objects (Pro Git)
Категории: