# Дерево и граф

> Графы описывают объекты и связи между ними, деревья — их частный случай без циклов; на них построены файловые системы, индексы БД, маршрутизация, зависимости пакетов и сборки.

Источник: https://llmdocs.ru/wiki/trees-graphs/ · обновлено 2026-11-09 · лицензия CC BY-SA 4.0

- **Граф**: множество вершин и рёбер G = (V, E)
- **Дерево**: связный граф без циклов, n вершин и n − 1 рёбер
- **Представления**: список смежности, матрица смежности
- **Обходы**: поиск в ширину (BFS), поиск в глубину (DFS)
- **Классические алгоритмы**: Дейкстра, A*, топологическая сортировка, Крускал, Прим
- **Деревья в практике**: BST, AVL, красно-чёрное, B-дерево, куча, префиксное дерево
**Граф** — математическая модель объектов (**вершин**, узлов) и связей между ними (**рёбер**); формально G = (V, E). **Дерево** — частный случай графа: связный граф без циклов, в котором между любыми двумя вершинами ровно один путь. Обе модели относятся к базовым [структурам данных](https://llmdocs.ru/wiki/data-structures.md): графами описывают дороги, сети, социальные связи и зависимости пакетов, деревьями — файловые системы, HTML-документы, индексы баз данных и синтаксис программ.[1]

## Графы

### Виды

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

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

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

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

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

### Обходы

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

```python
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-дерево](https://llmdocs.ru/wiki/b-tree.md)** и B+-дерево — сильно ветвящиеся деревья, оптимизированные под чтение страницами с диска; основа индексов [PostgreSQL](https://llmdocs.ru/wiki/postgresql.md), SQLite и файловых систем.
- **Куча** (heap) — дерево, где родитель не больше детей; очередь с приоритетом за O(log n), хранится в массиве (`heapq` в Python).
- **Префиксное дерево** (trie) — поиск по префиксу строки: автодополнение, маршрутизация URL и IP-адресов.
- **Синтаксические деревья** (AST) — промежуточное представление программы в [компиляторах и интерпретаторах](https://llmdocs.ru/wiki/compiler-interpreter.md); DOM — дерево HTML-документа.

В отличие от [хеш-таблицы](https://llmdocs.ru/wiki/hash-table.md), упорядоченные деревья позволяют обходить ключи по порядку и искать диапазоны («все заказы с 1 по 15 ноября»), ценой O(log n) вместо O(1) на операцию.

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

- файловая система — дерево каталогов (жёсткие и символические ссылки делают её графом);
- DNS — дерево доменных зон;
- маршрутизация в сетях — поиск кратчайших путей (OSPF использует Дейкстру);
- системы сборки, [CI/CD](https://llmdocs.ru/wiki/ci-cd.md)-пайплайны и оркестраторы задач — DAG;
- графовые базы данных и графы знаний, рекомендательные системы;
- сборщики мусора обходят граф объектов, начиная с корней (см. [Сборка мусора](https://llmdocs.ru/wiki/garbage-collection.md)).

## См. также

- [Алгоритм и O-нотация](https://llmdocs.ru/wiki/big-o.md)
- [Хеш-таблица](https://llmdocs.ru/wiki/hash-table.md)
- [Рекурсия](https://llmdocs.ru/wiki/recursion.md)
- [Структуры данных](https://llmdocs.ru/wiki/data-structures.md)

## Источники

1. [Cormen et al. — Introduction to Algorithms, 4th ed., parts III and VI (MIT Press)](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/)
2. [Sedgewick, Wayne — Algorithms, 4th ed., ch. 3–4](https://algs4.cs.princeton.edu/home/)
3. [Dijkstra — A note on two problems in connexion with graphs (1959)](https://doi.org/10.1007/BF01386390)
4. [Python — graphlib.TopologicalSorter](https://docs.python.org/3/library/graphlib.html)
5. [NetworkX documentation](https://networkx.org/documentation/stable/)
6. [Git — Git Objects (Pro Git)](https://git-scm.com/book/en/v2/Git-Internals-Git-Objects)