14. Алгоритмы на деревьях¶

14.1 Обходы деревьев¶

Введение¶

Дерево — это связный граф без циклов. В задачах на деревья ключевую роль играют обходы — способы пройти по всем вершинам в определённом порядке.

Обходы лежат в основе большинства алгоритмов на деревьях: поиска, подсчётов, динамики, обработки запросов.

Основные виды обходов¶

1. Обход в глубину (DFS)¶

Идея: мы идём как можно глубже по дереву, прежде чем возвращаться назад.

Интуиция: представьте лабиринт — вы идёте вперёд, пока не упрётесь, затем возвращаетесь назад и пробуете другой путь.

Порядки обхода:

• Вход в вершину (preorder)
• Обход поддерева
• Выход из вершины (postorder)

Пример дерева:

graph TD
1 --> 2
1 --> 3
2 --> 4
2 --> 5

DFS (postorder): 4 → 5 → 2 → 3 → 1

2. Обход в ширину (BFS)¶

Идея: мы обходим дерево по уровням.

Интуиция: сначала все вершины на расстоянии 1, затем на расстоянии 2 и т.д.

Пример:

BFS: 1 → 2 → 3 → 4 → 5

Зачем нужны обходы¶

Обходы используются для:

• подсчёта размеров поддеревьев
• поиска расстояний
• проверки свойств
• динамики на деревьях
• построения путей

Реализация DFS (C++)¶

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<int>> g;
vector<bool> used;

void dfs(int v) {
    used[v] = true;
    cout << v << " ";
    for (int to : g[v]) {
        if (!used[to]) dfs(to);
    }
}

int main() {
    cin >> n;
    g.resize(n + 1);
    used.assign(n + 1, false);

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
}

Реализация BFS (C++)¶

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<bool> used(n + 1, false);
    queue<int> q;

    q.push(1);
    used[1] = true;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        cout << v << " ";

        for (int to : g[v]) {
            if (!used[to]) {
                used[to] = true;
                q.push(to);
            }
        }
    }
}

Пример с ручным разбором¶

Дано дерево:

1 соединена с 2 и 3 2 соединена с 4 и 5

DFS: 1 → 2 → 4 → назад → 5 → назад → 3

BFS: 1 → 2 → 3 → 4 → 5

Связь с алгоритмом Дейкстры¶

Хотя Дейкстра применяется к графам с весами, идея выбора вершины похожа на BFS.

Идея¶

Мы всегда выбираем вершину с минимальным расстоянием от старта.

Как происходит выбор¶

• храним текущие расстояния
• используем очередь с приоритетом
• каждый раз берём вершину с минимальным расстоянием

Почему алгоритм корректен¶

Если все веса неотрицательные:

• как только вершина выбрана, её расстояние уже оптимально
• потому что нельзя найти более короткий путь через более длинные пути

Ограничения¶

Алгоритм не работает с отрицательными рёбрами

Сложность¶

• с кучей: O((n + m) log n)

Типичные ошибки¶

• забывают отмечать вершины посещёнными
• делают DFS без проверки used
• путают порядок обхода
• используют рекурсию без увеличения стека
• забывают, что дерево — неориентированный граф

Когда использовать¶

Используйте DFS, когда:

• нужно обработать поддеревья
• нужна рекурсия
• нужна постобработка

Используйте BFS, когда:

• нужны кратчайшие расстояния в невзвешенном графе
• нужен обход по уровням

Итог¶

Обходы деревьев — базовый инструмент. Почти любая задача на деревья сводится к правильному обходу и аккуратному хранению информации в процессе.