← вся теориятеория к собесу · Алгоритмы и структуры данных

Деревья, графы и рекурсия

Зачем это спрашивают

Деревья и графы - вторая ступень лайвкодинга. Проверяют владение двумя обходами и одним рекурсивным шаблоном, и этого хватает на удивление далеко: большинство задач про деревья - один и тот же паттерн, переодетый в разные условия.

Типовые формулировки: «найди глубину дерева», «сколько островов на карте», «минимальное число шагов до выхода из лабиринта».

// Шаблон стоит выучить дословно, как считалочку: реши для детей, собери у родителя. Высота, сумма, диаметр, проверка баланса - всё это буквально он, меняется только строчка сборки.

Граф, дерево и три обхода

Сначала про граф, раз всё дальнейшее про него. Граф - это вершины и рёбра между ними: города и дороги, юзеры и подписки, страницы и ссылки. Связным его называют, когда из любой вершины можно добраться до любой другой. Дерево - частный случай: связный граф без циклов. У дерева на n вершин ровно n − 1 ребро, и между любыми двумя вершинами существует ровно один путь. Отсюда и его удобство - заблудиться негде.

Обходы бинарного дерева отличаются одним: в какой момент обрабатывается сам узел относительно своих поддеревьев. Pre-order - сначала узел, потом дети. In-order - левое поддерево, узел, правое. Post-order - оба поддерева, потом узел.

Разница не академическая. Возьми дерево, где корень 2, слева 1, справа 3. Pre-order даст 2, 1, 3 - им удобно копировать и сериализовать дерево, потому что корень известен первым. In-order даст 1, 2, 3, то есть строго по возрастанию, и это свойство любого корректного дерева поиска. Post-order даст 1, 3, 2 - им считают всё, что зависит от детей: высоту, сумму, удаление узлов.

// Рекурсия по дереву - это почти всегда post-order: спускаемся к листьям, получаем ответы поддеревьев, комбинируем их у родителя. Если удаётся сформулировать «что мне нужно от левого и правого ребёнка», задача решена.

лист: узел без детей. База рекурсии почти всегда формулируется через листья или через пустое поддерево

Обход вширь и вглубь

Оба обхода отличаются одной структурой данных, и из неё следует всё остальное. Обход вширь (BFS, breadth-first search) держит очередь и потому разбирает вершины по слоям: сначала все соседи старта, потом все соседи соседей. Обход вглубь (DFS, depth-first search) держит стек - явный или неявный, через рекурсию - и уходит по одной ветке до упора, потом возвращается.

Из очереди следует главная гарантия обхода вширь: в невзвешенном графе он находит кратчайший путь. Просто потому, что вершины на расстоянии два не будут рассмотрены раньше, чем закончатся вершины на расстоянии один. Любая задача со словами «минимальное число шагов» - это он.

Обход вглубь берут там, где нужна структура, а не расстояние: компоненты связности, поиск циклов, топологическая сортировка, перебор с возвратом. Обе сложности одинаковы, O(V + E) - каждая вершина и каждое ребро трогаются по разу.

// На графе, в отличие от дерева, множество посещённых вершин обязательно. Без него первый же цикл превращает обход в вечный: A ведёт в B, B обратно в A, и так до конца времён. На дереве это прощалось, потому что циклов там нет по определению.

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

Как хранить граф и где он прячется

Список смежности - выбор по умолчанию: для каждой вершины хранится список её соседей. Памяти уходит O(V + E), перебор соседей мгновенный. Матрица смежности - таблица V на V, где на пересечении стоит признак наличия ребра. Она ест O(V²) памяти и оправдана только на плотных графах или когда критичен мгновенный ответ на вопрос «есть ли ребро между этими двумя».

Считать полезно так: у разреженных графов рёбер сильно меньше, чем V², а разреженных в задачах подавляющее большинство. Тысяча вершин и три тысячи рёбер - это три тысячи ячеек списка против миллиона ячеек матрицы.

Отдельно стоит натренировать глаз на замаскированные графы. Сетка в задаче про лабиринт или карту островов - это тот же граф: клетка есть вершина, соседство по стороне есть ребро. Задача «посчитай острова» на самом деле называется «посчитай компоненты связности», и решается обычным обходом.

// Ещё чаще граф прячется в отношениях: «кто кому подчиняется», «какой модуль что импортирует», «какой курс требует какого». Как только видишь такое, вспоминай обходы и топологическую сортировку.

Как отвечать: «Чем обход вширь отличается от обхода вглубь и когда какой брать?»

Отличаются структурой и, как следствие, гарантией. Вширь идёт очередью по слоям и потому даёт кратчайший путь в невзвешенном графе - любая формулировка про минимальное число шагов это он. Вглубь идёт стеком или рекурсией и удобен там, где важна структура: компоненты, поиск циклов, топологическая сортировка, перебор с возвратом. Сложность у обоих O(V + E), так что выбор диктует вопрос задачи, а не скорость. Две обязательные детали: на графе нужно множество посещённых, иначе цикл зациклит обход; и рекурсивный обход вглубь на миллионах вершин переполнит стек, там я пишу итеративно со своим стеком. И оговорюсь про границу: если рёбра взвешенные, обход вширь кратчайший путь уже не гарантирует, там нужен Дейкстра.

Выбор объяснён через гарантию, а не через список применений. Плюс обе ловушки реализации и честно названная граница применимости - как раз то, о чём спросят следующим вопросом.

На чём валят

−Забыть множество посещённых на графе: на дереве прокатывало, здесь получается вечный цикл.
−Считать, что «кратчайший путь - это всегда обход вширь»: на взвешенном графе нужен Дейкстра.
−Проверять дерево поиска сравнением только с непосредственным родителем: нарушение через уровень так не ловится.
−Писать рекурсивный обход вглубь на миллионах вершин: стек переполнится, в Python предел около тысячи вложенных вызовов.
−Обойти граф из одной вершины и решить, что покрыл весь: несвязные компоненты требуют внешнего цикла по всем вершинам.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 17, остальные разбираются в тренажёре.

#trees_graphs_recursion1 / 5
Рекурсивный DFS на графе с миллионами вершин в Python рискует упасть. Чем именно и как быть?
A)Переполнением динамической кучи объектов; помогает просто увеличить объём оперативной памяти машины
B)Переполнением стека вызовов (RecursionError); переписать на итеративный DFS с явным стеком
C)Ничем не рискует — Python сам разворачивает рекурсию в цикл
D)Утечкой памяти в garbage collector
показать ответ и разбор
+B)Переполнением стека вызовов (RecursionError); переписать на итеративный DFS с явным стеком
// разбор: Глубина рекурсии = глубина обхода; в Python лимит (обычно ~1000) защищает от переполнения стека интерпретатора, глубокий DFS упирается в RecursionError. sys.setrecursionlimit лишь отодвигает границу и рискует настоящим C-stack overflow. Надёжное решение — итеративный DFS с явным стеком (list) в куче: глубина ограничена только памятью.
#trees_graphs_recursion2 / 5
Дейкстра ищет кратчайшие пути. Зачем в ней куча (priority queue) и когда алгоритм неприменим?
A)Куча нужна для красоты; алгоритм работает на графах без ограничений
B)Куча сортирует граф; неприменим для деревьев
C)Куча хранит посещённые вершины; неприменим, если рёбер меньше вершин
D)Куча каждый раз даёт ближайшую необработанную вершину за O(log V); алгоритм ломается при отрицательных весах рёбер
показать ответ и разбор
+D)Куча каждый раз даёт ближайшую необработанную вершину за O(log V); алгоритм ломается при отрицательных весах рёбер
// разбор: Дейкстра жадно расширяет ближайшую по текущей оценке вершину; min-heap выдаёт её за O(log V), давая общую сложность O((V+E) log V). Жадность корректна только при неотрицательных весах: отрицательное ребро может улучшить уже «финализированную» вершину, и инвариант рушится. Для отрицательных весов берут Беллмана — Форда (O(V·E)).
#trees_graphs_recursion3 / 5
Из чего состоит граф и чем ориентированный отличается от неориентированного?
A)Из вершин и рёбер; в ориентированном у ребра есть направление
B)Из узлов и листьев; в ориентированном рёбра ведут от корня к листьям
C)Из ключей и значений; ориентированный хранит порядок вставки
D)Из вершин и рёбер; ориентированный связный, а неориентированный нет
показать ответ и разбор
+A)Из вершин и рёбер; в ориентированном у ребра есть направление
// разбор: Граф — множество вершин и рёбер между ними. Ребро неориентированного графа ходится в обе стороны (дружба), ребро ориентированного — в одну (подписка, ссылка). Дерево — частный случай связного графа без циклов. Отсутствие циклов — отдельное свойство: в орграфе они встречаются, и тогда топологическая сортировка невозможна.
#trees_graphs_recursion4 / 5
В дереве n узлов. Сколько в нём рёбер и почему?
A)n − 1: у каждого узла, кроме корня, ровно один родитель
B)n: каждый узел соединён со следующим по обходу
C)2n − 1: у каждого узла по два потомка
D)Зависит от того, бинарное это дерево или нет
показать ответ и разбор
+A)n − 1: у каждого узла, кроме корня, ровно один родитель
// разбор: Каждое ребро — это связь «родитель — потомок», а родитель есть у всех узлов, кроме корня. Значит рёбер ровно n − 1, независимо от формы и арности дерева. Обратное тоже полезно помнить: связный граф на n вершинах с n − 1 ребром обязан быть деревом, а добавление любого ребра создаёт в нём ровно один цикл.
#trees_graphs_recursion5 / 5
Обход графа дружбы собирает достижимых пользователей и падает на проде:
```
def reach(g, v, acc):
    acc.add(v)
    for u in g[v]:
        reach(g, u, acc)
    return acc
```
Найди причину:
A)Перед рекурсией нет проверки посещённости — взаимная дружба зациклит спуск
B)set не годится как аккумулятор: add внутри рекурсии создаёт копию на каждом уровне
C)Итерация по g[v] мутирует граф во время обхода — словарь меняет размер и падает
D)Результат вложенных reach никуда не присваивается — накопленное теряется
показать ответ и разбор
+A)Перед рекурсией нет проверки посещённости — взаимная дружба зациклит спуск
// разбор: Марка ставится (acc.add), но перед спуском никто не проверяет, стоит ли она у соседа: пара взаимных друзей гоняет рекурсию v → u → v до RecursionError. Лечится одной строкой в начале: if v in acc: return acc. Тогда каждая вершина раскрывается один раз, обход становится O(V + E). На очень глубоких графах дополнительно спасает итеративный DFS со стеком вместо рекурсии.

дальше

Теорию прочитали. Навык ставится повторением

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

Открыть тренажёр Вся тема: Алгоритмы и структуры данных