Ключевые термины
DFS (поиск в глубину)
Алгоритм обхода графа, который рекурсивно или итеративно проходит по всем вершинам, проверяя соседей в фиксированном порядке: вверх, вправо, вниз, влево.
Компонента связности
Область клеток с одинаковыми номерами, которые находятся сверху, справа, снизу или слева на расстоянии одной клетки.
Рекурсия
Ситуация, когда функция вызывает саму себя.
Переполнение стека
Ошибка, возникающая при превышении допустимой глубины рекурсии, когда стековая память заканчивается.
Итеративная реализация
Способ реализации алгоритма без рекурсии, с использованием явного стека для хранения порядка обхода.
Big O
Оценка сложности алгоритма по времени и памяти, игнорирующая константы.
BFS (Breadth-First Search, поиск в ширину)
Алгоритм обхода графа, который одновременно исследует все направления, растекаясь равномерно, и всегда находит кратчайший путь в лабиринтах.
DFS (Depth-First Search, поиск в глубину)
Алгоритм обхода графа, который проваливается в глубину, а потом откатывается назад; технически может найти путь, но на больших полях работает медленно, перебирая все пути.
Очередь (Queue)
Структура данных, работающая по принципу FIFO (first in, first out): элемент, добавленный первым, выходит первым. Используется в BFS.
FIFO (First In, First Out)
Принцип работы очереди: первым вошёл, первым вышел.
Multisource BFS
Вариант BFS, в котором в очередь помещаются несколько стартовых точек (источников), и одна волна поиска распространяется от всех источников одновременно, позволяя найти ближайший источник за один обход.
prev (родительская ссылка)
Словарь, где ключ — координата клетки, значение — координата клетки, из которой пришли в данную. Используется для восстановления кратчайшего маршрута после BFS.
BFS (поиск в ширину)
Алгоритм обхода графа, который решает все рассмотренные задачи: заливку, проверку пути, поиск кратчайшего расстояния, восстановление маршрута и задачу со скорой помощью. Расходует память контролируемо.
DFS (поиск в глубину)
Алгоритм обхода графа, который оптимально решает только заливку и проверку существования пути. Рекурсивный вариант прост в запоминании, но рискован переполнением стека.
Рекурсивный DFS
Реализация поиска в глубину с использованием рекурсии; легко запоминается (5-10 строк кода), но при больших входных данных возможен риск переполнения стека.
Нерекурсивный DFS
Реализация поиска в глубину без рекурсии; позволяет избежать переполнения стека, но вероятность пика потребления памяти в N остаётся высокой.
Переполнение стека
Риск, возникающий при использовании рекурсивного DFS на больших входных данных, когда стек вызовов превышает допустимый размер.
Карточки
Как компьютер представляет лабиринт для алгоритмов поиска пути?
Компьютер видит лабиринт как матрицу из нулей и единиц, где 0 — свободная клетка, а 1 — стена. Старт и финиш задаются координатами (номер строки и номер колонки).
Что такое компонента связности в контексте лабиринта?
Компонента связности — это область одинаковых клеток, соединённых по четырём направлениям (вверх, вправо, вниз, влево) на расстоянии одной клетки.
Почему алгоритм DFS (поиск в глубину) должен возвращаться назад, если все соседние клетки уже посещены или являются стенами?
DFS должен возвращаться к предыдущей клетке, чтобы попробовать другие направления, в которых он ещё не ходил. Это необходимо, чтобы не пропустить возможный путь к финишу, так как без возврата можно упустить правильный маршрут.
Как проверить с помощью DFS, существует ли путь от старта до финиша в лабиринте?
Запустить DFS из стартовой точки. Если алгоритм обойдёт все четыре направления из точки старта и не найдёт финиш, то пути не существует. Если финиш найден, путь существует.
Какие шаги выполняет рекурсивная функция DFS при проверке клетки?
1. Проверить, не выходят ли координаты за границу поля, не попадают ли на стену или в уже посещённую клетку. Если да — вернуть false. 2. Если текущая клетка совпадает с финишем — вернуть true. 3. Пометить клетку как посещённую. 4. Рекурсивно попробовать двигаться вверх, вправо, вниз, влево, возвращая true, если хотя бы в одном направлении удалось дойти до финиша.
Почему при поиске пути в лабиринте сначала проверяют существование пути, а не сразу ищут кратчайший?
Поиск кратчайшего пути — более сложная задача, к которой нужно подготовиться. Поэтому сначала учатся проверять, существует ли вообще путь от точки А до точки Б, а затем уже переходят к поиску кратчайшего.
Какие три ключевых шага выполняет DFS при обходе клеток?
Проверить, стоит ли посещать клетку, обработать саму клетку, пройтись по соседним клеткам.
Как подсчитать количество компонент связности (заливок) на поле с помощью DFS?
Пройти по всем клеткам поля, начиная с левого верхнего угла. Если клетка не посещена, запустить из неё DFS для обхода всех соседей того же цвета и увеличить счётчик компонент на один. Повторять до конца поля.
Почему рекурсивный DFS может вызвать переполнение стека на больших матрицах?
При каждом рекурсивном вызове расходуется память на стеке. В Python глубина рекурсии ограничена примерно 1000 вызовами, и если компонента связности содержит более 1000 клеток, происходит ошибка рекурсии (переполнение стека).
Какие два способа решения проблемы переполнения стека при рекурсивном DFS упоминаются в материале?
Первый: увеличить размер стековой памяти. Второй: переписать алгоритм на итеративную реализацию, избавившись от рекурсии.
Как реализовать итеративный DFS для обхода клеток, используя явный стек?
Создать переменную-стек, поместить в неё стартовую клетку и сразу пометить её как посещённую. Пока стек не пуст, доставать последнюю вершину, обходить четырёх соседей (вверх, вправо, вниз, влево) и добавлять в стек те, которые не выходят за границы, совпадают по цвету и ещё не посещены, сразу помечая их как посещённые.
Почему оценка сложности DFS по времени и памяти для матрицы N x M составляет O(N*M)?
В худшем случае каждая клетка обходится до четырёх раз (сверху, снизу, слева, справа) плюс запуск DFS из каждой клетки, что даёт примерно 5*N*M операций, но константы в Big O не учитываются, поэтому время O(N*M). Память тратится на хранение порядка обхода вершин (в рекурсивной версии — стек вызовов, в итеративной — структура данных стек), и в худшем случае в стеке могут оказаться все элементы матрицы, поэтому память также O(N*M).
Какую реализацию DFS стоит выбрать на собеседовании, если вы уверены в итеративной версии?
Если вы уверены в итеративной реализации, лучше выбрать её, так как это может произвести впечатление на интервьюера. Однако рекурсивная реализация также обычно приемлема, и за неё баллы не снимают.
Назовите два ключевых применения DFS, которые упоминаются в материале.
Первое — проверка, существует ли путь от точки А до точки B. Второе — подсчёт числа компонент связности.
Почему DFS не подходит для поиска кратчайшего пути в лабиринте, а BFS подходит?
DFS проваливается в глубину и перебирает все возможные пути, даже самые бессмысленные, поэтому на больших полях работает ужасно медленно. BFS распространяется во все стороны равномерно и за один проход находит кратчайшее расстояние от точки A до B.
Какую структуру данных использует BFS и по какому принципу она работает?
BFS использует очередь. Принцип работы: первый вошёл — первый вышел (FIFO). Элемент добавляется в конец очереди, а удаляется из начала. Главное требование — операции добавления в конец и удаления из начала должны выполняться за O(1).
Как инициализировать BFS перед началом поиска кратчайшего пути?
Создаётся массив dist размером n x m, где все клетки изначально имеют значение -1 (не посещены). Стартовая клетка получает расстояние 0. Затем создаётся очередь, в которую помещается стартовая клетка.
Опишите шаг обработки текущей клетки в BFS.
Извлекаем первую клетку из очереди. Если это финиш B, возвращаем расстояние. Иначе смотрим четырёх соседей: сверху, справа, снизу, слева. Для каждого соседа проверяем три фильтра: не выходит за границы, не является стеной, ещё не посещён. Если все условия выполнены, записываем расстояние до соседа как расстояние до текущей плюс 1 и добавляем соседа в очередь.
Почему клетку нужно помечать как посещённую сразу при добавлении в очередь, а не при извлечении?
Если помечать клетку при извлечении, то одна и та же клетка может быть добавлена в очередь несколько раз, что замедлит алгоритм. При немедленной отметке клетка попадает в очередь ровно один раз и обрабатывается ровно один раз.
Чем отличается нерекурсивный BFS от нерекурсивного DFS?
Разница всего в одной строке: в DFS вершины кладутся в стек, а в BFS — в очередь. Из-за этого DFS уходит вглубь, а BFS растекается вширь, что позволяет BFS находить кратчайший путь.
Какова временная сложность BFS для матрицы размером N x M?
Инициализация массива dist занимает O(N*M). Сам BFS в худшем случае посещает каждую клетку один раз, что даёт ещё O(N*M). Итого 2*N*M, константа отбрасывается, получаем O(N*M).
Какова оценка памяти BFS для матрицы N x M?
Память складывается из массива dist (N*M) и очереди. В худшем случае (например, H-фрактал) очередь может вырасти почти до N*M. Итого примерно 2*N*M, константа отбрасывается, получаем O(N*M).
Как восстановить кратчайший путь от старта до финиша после выполнения BFS?
При переходе в соседнюю клетку запоминаем, из какой клетки пришли (prev). После достижения финиша идём по цепочке prev от финиша к старту, помечая клетки как часть маршрута.
Почему добавление prev для восстановления пути не меняет асимптотическую оценку времени и памяти BFS?
Время: обход всех клеток O(N*M) + восстановление пути O(N*M) = O(N*M). Память: массив dist O(N*M) + словарь prev O(N*M) + очередь O(N*M) = O(N*M). Константы опускаются, поэтому асимптотика остаётся O(N*M).
Как работает Multisource BFS для поиска ближайшей клиники?
В очередь помещаются координаты всех клиник, каждая помечается как посещённая. Запускается одна волна BFS. При обработке клетки, если это пациент, возвращается координата клиники-источника. Если нет, все свободные непосещённые соседи получают ту же клинику-источник и добавляются в очередь. Если очередь опустела, пути нет.
Чем отличается запуск BFS от пациента до первой клиники от Multisource BFS для задачи поиска ближайшей клиники?
Multisource BFS запускает волну от всех клиник одновременно, а альтернатива — запустить BFS от пациента и остановиться при достижении первой клиники. Второй вариант проще и лаконичнее, но оба имеют одинаковую асимптотику O(N*M).
Какие основные задачи на графах решаются с помощью BFS и DFS?
Подсчёт количества компонент связности, заливка, проверка существования пути от A до B, поиск кратчайшего расстояния и восстановление пути.
Какие задачи оптимально решает DFS, а какие — BFS?
DFS оптимально решает только заливку и проверку существования пути. BFS решает все перечисленные задачи: заливку, проверку существования пути, поиск кратчайшего расстояния, восстановление маршрута и задачу со скорой помощью.
Почему рекурсивный DFS часто используется кандидатами на собеседованиях?
Потому что его проще всего запомнить: 5–10 строк кода, и решение готово.
Какие риски связаны с рекурсивным DFS, нерекурсивным DFS и BFS?
Рекурсивный DFS рискует переполнением стека при больших входных данных. Нерекурсивный DFS избегает переполнения стека, но сохраняет высокую вероятность пикового потребления памяти O(N). BFS расходует память более контролируемо, и худшие случаи встречаются редко.
Какую реализацию обхода предпочитают опытные интервьюеры, а какую — менее опытные?
Опытные интервьюеры почти всегда предпочитают BFS. Менее опытные (более зелёные) обычно предлагают не усложнять и написать DFS.
Тест с объяснениями
Какую первую задачу решают алгоритмы на графах при поиске пути в лабиринте?
- Определить количество тупиков в лабиринте
- Проверить, существует ли вообще путь от старта до финиша
- Построить матрицу смежности для всего поля
- Сразу найти кратчайший маршрут
Ответ и объяснение
Проверить, существует ли вообще путь от старта до финиша
Правильный вариант: сначала проверяют существование пути, а не ищут кратчайший. Остальные варианты неверны: кратчайший путь ищут позже, матрица смежности не строится, количество тупиков не является первой задачей.
Как компьютер представляет лабиринт для алгоритмов поиска пути?
- Как матрицу из нулей и единиц, где 0 — свободная клетка, 1 — стена
- Как набор координат всех стен и проходов в текстовом файле
- Как изображение в формате PNG, которое анализируется попиксельно
- Как список всех возможных маршрутов от старта до финиша
Ответ и объяснение
Как матрицу из нулей и единиц, где 0 — свободная клетка, 1 — стена
Правильный вариант: компьютер видит поле как матрицу из нулей (свободные клетки) и единиц (стены). Остальные варианты неверны: список маршрутов не хранится, изображение не анализируется, текстовый файл с координатами не используется.
В каком фиксированном порядке алгоритм DFS проверяет соседние клетки?
- Вправо, вверх, влево, вниз
- Вверх, вправо, вниз, влево
- Влево, вниз, вправо, вверх
- Вверх, вниз, влево, вправо
Ответ и объяснение
Вверх, вправо, вниз, влево
Правильный вариант: сначала вверх, потом вправо, затем вниз, наконец влево. Остальные варианты неверны: порядок строго определён и не меняется.
Что делает алгоритм DFS, когда все соседние клетки уже посещены или являются стенами?
- Останавливается и сообщает, что путь не найден
- Начинает обход заново с другой стартовой точки
- Пропускает эту клетку и переходит к следующей по порядку
- Возвращается к предыдущей клетке, чтобы попробовать другие направления
Ответ и объяснение
Возвращается к предыдущей клетке, чтобы попробовать другие направления
Правильный вариант: алгоритм возвращается к предыдущей клетке, чтобы попробовать другие направления, в которых он ещё не ходил. Остальные варианты неверны: остановка происходит только после обхода всех направлений из старта, обход не начинается заново, клетка не пропускается.
Как проверить с помощью DFS, существует ли путь от старта до финиша в лабиринте?
- Посчитать количество стен между стартом и финишем
- Построить кратчайший маршрут и проверить, не прерывается ли он стенами
- Сравнить координаты старта и финиша по строкам и столбцам
- Обойти все клетки, доступные из старта; если финиш не найден — пути нет
Ответ и объяснение
Обойти все клетки, доступные из старта; если финиш не найден — пути нет
Правильный вариант: DFS обходит все клетки, доступные из старта; если финиш не найден, пути нет. Остальные варианты неверны: количество стен не определяет существование пути, кратчайший маршрут не строится, сравнение координат не даёт информации о проходимости.
Какие шаги выполняет рекурсивная функция DFS при проверке клетки?
- Проверка только границ и стены; если всё в порядке — сразу переход к соседям
- Проверка границ, стены и посещённости; проверка достижения финиша; пометка клетки посещённой; рекурсивный обход соседей
- Обход соседей; затем проверка границ, стены и финиша; пометка клетки посещённой
- Пометка клетки посещённой; затем проверка границ, стены и финиша; обход соседей
Ответ и объяснение
Проверка границ, стены и посещённости; проверка достижения финиша; пометка клетки посещённой; рекурсивный обход соседей
Правильный вариант: сначала проверяются границы, стена и посещённость; затем проверяется достижение финиша; клетка помечается посещённой; после этого рекурсивно обходятся соседи. Остальные варианты неверны: порядок действий строго определён и не может быть изменён.
Что такое компонента связности в контексте лабиринта?
- Путь от старта до финиша, не содержащий тупиков
- Набор клеток, которые можно посетить, не возвращаясь назад
- Множество всех стен, окружающих свободное пространство
- Область одинаковых клеток, соединённых по четырём направлениям
Ответ и объяснение
Область одинаковых клеток, соединённых по четырём направлениям
Правильный вариант: компонента связности — это область одинаковых клеток, соединённых по четырём направлениям (вверх, вправо, вниз, влево). Остальные варианты неверны: стены не образуют компоненту связности, путь от старта до финиша — это маршрут, а не область, набор клеток без возврата не является компонентой.
Какие три ключевых шага определяют поведение DFS при обходе клеток?
- Выбор цвета области, запуск рекурсии и увеличение счётчика заливок
- Проверка допустимости посещения клетки, обработка клетки и обход соседних клеток
- Проверка границ поля, сортировка соседей и возврат к стартовой клетке
- Пометка клетки как посещённой, поиск кратчайшего пути и подсчёт компонент
Ответ и объяснение
Проверка допустимости посещения клетки, обработка клетки и обход соседних клеток
DFS строится на трёх правилах: проверить, стоит ли посещать клетку, обработать саму клетку и пройтись по соседним клеткам. Остальные варианты смешивают шаги с другими операциями или добавляют действия, не входящие в эти три правила.
При каких условиях DFS не заходит в соседнюю клетку и возвращается назад?
- Клетка выходит за границу поля, имеет другой цвет или уже была посещена
- Клетка является стартовой или находится в правом нижнем углу
- Клетка находится в другом ряду или столбце, чем текущая
- Клетка ещё не посещена и совпадает по цвету с текущей
Ответ и объяснение
Клетка выходит за границу поля, имеет другой цвет или уже была посещена
Выход за границу поля, другой цвет клетки или её посещённость — это условия, при которых DFS не заходит в клетку и возвращается назад. Непосещённая клетка того же цвета, наоборот, подлежит обходу, а расположение в другом ряду или столбце само по себе не является препятствием.
Как алгоритм подсчитывает количество компонент связности (заливок) на поле?
- Проходит по всем клеткам и запускает DFS из каждой ещё не посещённой клетки, увеличивая счётчик на единицу
- Запускает DFS из правого нижнего угла и считает количество возвратов назад
- Запускает DFS из левого верхнего угла и считает все встреченные клетки
- Проходит по полю и увеличивает счётчик для каждой клетки другого цвета
Ответ и объяснение
Проходит по всем клеткам и запускает DFS из каждой ещё не посещённой клетки, увеличивая счётчик на единицу
Счётчик увеличивается на единицу только при запуске DFS из непосещённой клетки, что соответствует новой области. Запуск из одной клетки или подсчёт всех клеток не даёт числа областей, а возвраты назад не отражают количество компонент.
Почему после обхода одной области алгоритм не запускает DFS из уже посещённых клеток?
- Эти клетки имеют другой цвет, чем текущая область
- Эти клетки являются стенами и не подлежат обходу
- Эти клетки уже входят в обойдённую область, поэтому повторный запуск не нужен
- Эти клетки находятся за границей поля
Ответ и объяснение
Эти клетки уже входят в обойдённую область, поэтому повторный запуск не нужен
Клетки, обойдённые DFS, уже принадлежат найденной области, поэтому алгоритм просто идёт дальше до новой непосещённой клетки. Другой цвет, граница поля или стены — это другие условия, не связанные с причиной пропуска уже посещённых клеток.
Почему рекурсивный DFS может вызвать ошибку переполнения стека на большой матрице?
- DFS хранит все клетки матрицы в отдельном массиве, размер которого превышает память
- Каждый рекурсивный вызов расходует память на стеке, а глубина рекурсии ограничена примерно тысячей вызовов
- Каждый рекурсивный вызов расходует память в куче, которая не ограничена
- DFS запускает рекурсию только для клеток другого цвета, и их слишком много
Ответ и объяснение
Каждый рекурсивный вызов расходует память на стеке, а глубина рекурсии ограничена примерно тысячей вызовов
При рекурсивном вызове расходуется стековая память, и в Python глубина рекурсии по умолчанию ограничена примерно тысячей вызовов. Куча не является местом расхода при рекурсивных вызовах, а ограничение связано именно с конечностью стека, а не с массивом посещений или цветом клеток.
Какие два способа решения проблемы переполнения стека при рекурсивном DFS упоминаются в материале?
- Уменьшить размер матрицы или увеличить глубину рекурсии
- Заменить стек на кучу или запускать DFS только из угловых клеток
- Отключить проверку посещённых клеток или использовать другой цвет
- Увеличить размер стековой памяти или переписать алгоритм на итеративную реализацию
Ответ и объяснение
Увеличить размер стековой памяти или переписать алгоритм на итеративную реализацию
Материал называет два способа: увеличить размер стековой памяти и перейти на итеративную реализацию без рекурсии. Уменьшение матрицы, замена стека на кучу, отключение проверки посещений и запуск только из углов не решают проблему переполнения стека.
Почему итеративная реализация DFS считается предпочтительнее увеличения размера стека?
- Она автоматически находит кратчайший путь между клетками
- Она позволяет обходить клетки без проверки границ поля
- Она избавляет от переполнения стека и ускоряет алгоритм за счёт отсутствия накладных расходов на вызовы функций
- Она уменьшает асимптотику по времени до O(1)
Ответ и объяснение
Она избавляет от переполнения стека и ускоряет алгоритм за счёт отсутствия накладных расходов на вызовы функций
Итеративная реализация устраняет рекурсию, снижает нагрузку на стек и убирает накладные расходы на вызовы функций, поэтому работает быстрее. Она не отменяет проверку границ, не ищет кратчайший путь и не даёт константную асимптотику.
Как в итеративной реализации DFS используется стек?
- В стек кладут координаты только после полного обхода всех соседей
- В стек добавляют только клетки другого цвета, не помечая их посещёнными
- В стек складывают все клетки матрицы заранее, а затем извлекают их по одной
- В стек сначала кладут стартовую клетку, а затем добавляют соседей, помечая вершину посещённой сразу при добавлении в стек
Ответ и объяснение
В стек сначала кладут стартовую клетку, а затем добавляют соседей, помечая вершину посещённой сразу при добавлении в стек
Стек хранит порядок обхода: сначала стартовая клетка, затем соседи, а вершина помечается посещённой сразу при добавлении, чтобы не обходить её повторно. Предварительное заполнение всех клеток, добавление только другого цвета или отложенная пометка не соответствуют описанной реализации.
Какие три условия проверяются перед добавлением соседней клетки в стек?
- Клетка ещё не посещена, находится в правом нижнем углу и совпадает по цвету
- Клетка не выходит за границы, является стартовой и имеет другой цвет
- Клетка находится в другом ряду, имеет другой цвет и уже посещена
- Клетка не выходит за границы, совпадает по цвету с текущей и ещё не посещена
Ответ и объяснение
Клетка не выходит за границы, совпадает по цвету с текущей и ещё не посещена
Перед добавлением в стек проверяют, что клетка в границах поля, её цвет совпадает с текущим и она ещё не посещена. Остальные варианты содержат неверные условия: другой цвет, посещённость или положение в углу не являются условиями добавления.
Почему временная сложность алгоритма DFS для поиска компонент связности на матрице N x M оценивается как O(N*M), а не как O(5*N*M)?
- Алгоритм никогда не обходит каждую клетку более одного раза.
- В Big O константы не учитываются, поэтому 5*N*M упрощается до O(N*M).
- Оценка O(5*N*M) точнее, но на собеседованиях принято указывать O(N*M).
- Константа 5 возникает только в итеративной версии, а в рекурсивной её нет.
Ответ и объяснение
В Big O константы не учитываются, поэтому 5*N*M упрощается до O(N*M).
Правильный вариант объясняет, что в нотации Big O константные множители отбрасываются, поэтому 5*N*M даёт асимптотику O(N*M). Вариант про однократный обход неверен: клетка может быть проверена до четырёх раз. Вариант про различие версий ошибочен: константа 5 относится к обеим реализациям. Вариант про точность неверен: в Big O константы не учитываются не только на собеседованиях, а по определению.
На что расходуется память в рекурсивной и итеративной версиях DFS при обходе матрицы?
- В рекурсивной версии память тратится на копирование матрицы, а в итеративной — на стек координат.
- В рекурсивной версии память не расходуется, так как вызовы функций не занимают места, а в итеративной — на стек.
- В обеих версиях память тратится на хранение порядка обхода вершин: в рекурсивной — стек вызовов функций, в итеративной — явный стек координат.
- В обеих версиях память тратится только на хранение самой матрицы, а стек не учитывается.
Ответ и объяснение
В обеих версиях память тратится на хранение порядка обхода вершин: в рекурсивной — стек вызовов функций, в итеративной — явный стек координат.
Правильный вариант верно описывает расход памяти: в рекурсивной версии — стек вызовов, в итеративной — явный стек. Вариант про копирование матрицы неверен: матрица не копируется. Вариант про отсутствие расхода памяти в рекурсии ошибочен: рекурсивные вызовы занимают стековую память. Вариант про только матрицу неверен: стек также потребляет память.
Какая оценка по памяти в худшем случае для DFS на матрице N x M и почему?
- O(N+M), потому что стек хранит только текущий путь, а не все вершины.
- O(log(N*M)), потому что глубина рекурсии логарифмическая.
- O(N*M), потому что в худшем случае в стеке могут оказаться все элементы матрицы.
- O(1), потому что алгоритм использует только фиксированное количество переменных.
Ответ и объяснение
O(N*M), потому что в худшем случае в стеке могут оказаться все элементы матрицы.
Правильный вариант указывает O(N*M) и объясняет причину: в худшем случае стек содержит все элементы матрицы. Вариант O(N+M) неверен: стек может содержать гораздо больше элементов, чем сумма размерностей. Вариант O(log(N*M)) ошибочен: глубина рекурсии может достигать N*M. Вариант O(1) неверен: алгоритм использует дополнительную память для стека.
Какая оценка сложности по времени и памяти является классической для DFS на матрице N x M и в каком проценте случаев она встречается?
- O(N*M) по времени и O(N+M) по памяти, встречается в 90% случаев.
- O(N*M) по времени и O(1) по памяти, встречается в 90% случаев.
- O(N*M) по времени и памяти, встречается в 90% случаев.
- O(N^2*M^2) по времени и O(N*M) по памяти, встречается в 50% случаев.
Ответ и объяснение
O(N*M) по времени и памяти, встречается в 90% случаев.
Правильный вариант верно указывает классическую оценку O(N*M) по времени и памяти и частоту 90%. Вариант с O(N+M) по памяти неверен: память оценивается как O(N*M). Вариант с O(N^2*M^2) ошибочен: это завышенная оценка. Вариант с O(1) по памяти неверен: алгоритм использует дополнительную память.
Какую реализацию DFS рекомендуется использовать на собеседовании, если кандидат уверен в итеративной версии?
- Рекурсивную, итеративная не применяется на собеседованиях
- Итеративную, это покажет глубокое понимание алгоритма
- Итеративную, только если рекурсивная вызывает переполнение стека
- Рекурсивную, так как она проще для понимания интервьюером
Ответ и объяснение
Итеративную, это покажет глубокое понимание алгоритма
Правильный вариант — итеративная реализация, если кандидат в ней уверен, так как это демонстрирует более высокий уровень владения алгоритмом. Остальные варианты неверны: рекурсивная реализация обычно приемлема, но не является предпочтительной при уверенности в итеративной; итеративная не требует переполнения стека для выбора; рекурсивная не является единственным вариантом.
Какие два ключевых применения DFS упоминаются в материале?
- Проверка связности графа и поиск мостов
- Обход графа в ширину и поиск циклов
- Проверка существования пути между двумя точками и подсчёт числа компонент связности
- Поиск кратчайшего пути и топологическая сортировка
Ответ и объяснение
Проверка существования пути между двумя точками и подсчёт числа компонент связности
Правильный вариант включает проверку существования пути от точки A до B и подсчёт числа компонент связности — именно эти два применения названы в материале. Остальные варианты содержат другие алгоритмы или задачи, не упомянутые в данном контексте.
Почему DFS не подходит для поиска кратчайшего пути в лабиринте, а BFS подходит?
- DFS проваливается в глубину и перебирает все возможные пути, что медленно, а BFS распространяется равномерно во все стороны и находит кратчайший путь за один проход.
- DFS может найти только один путь, а BFS находит все пути одновременно.
- DFS работает только на деревьях, а BFS — на любых графах.
- DFS использует очередь, что замедляет поиск, а BFS использует стек, что ускоряет его.
Ответ и объяснение
DFS проваливается в глубину и перебирает все возможные пути, что медленно, а BFS распространяется равномерно во все стороны и находит кратчайший путь за один проход.
Правильный вариант: DFS проваливается в глубину и перебирает все возможные пути, что медленно, а BFS распространяется равномерно во все стороны и находит кратчайший путь за один проход. Остальные варианты неверны: DFS использует стек, а BFS — очередь; DFS может найти путь, но не обязательно кратчайший; оба алгоритма работают на графах, не только на деревьях.
Какую структуру данных использует BFS и по какому принципу она работает?
- Очередь, работающую по принципу FIFO (первым вошёл — первым вышел).
- Массив, работающий по принципу произвольного доступа.
- Дек, работающий по принципу двустороннего доступа.
- Стек, работающий по принципу LIFO (последним вошёл — первым вышел).
Ответ и объяснение
Очередь, работающую по принципу FIFO (первым вошёл — первым вышел).
Правильный вариант: очередь, работающую по принципу FIFO (первым вошёл — первым вышел). Остальные варианты неверны: BFS использует очередь, а не стек; дек может использоваться, но основной принцип — FIFO; массив не обеспечивает нужного порядка обработки.
Как инициализировать BFS перед началом поиска кратчайшего пути?
- Создать массив расстояний dist, заполнить его -1, установить dist[старт] = 0 и не добавлять ничего в очередь.
- Создать массив расстояний dist, заполнить его -1, установить dist[старт] = 0 и поместить стартовую клетку в очередь.
- Создать массив расстояний dist, заполнить его 0, установить dist[старт] = 1 и поместить все клетки в очередь.
- Создать массив расстояний dist, заполнить его 0, установить dist[старт] = -1 и поместить стартовую клетку в стек.
Ответ и объяснение
Создать массив расстояний dist, заполнить его -1, установить dist[старт] = 0 и поместить стартовую клетку в очередь.
Правильный вариант: создать массив расстояний dist, заполнить его -1, установить dist[старт] = 0 и поместить стартовую клетку в очередь. Остальные варианты неверны: dist[старт] должно быть 0, а не 1 или -1; очередь должна содержать только стартовую клетку, а не все; BFS использует очередь, а не стек.
Опишите шаг обработки текущей клетки в BFS.
- Извлечь клетку из очереди, если это финиш — вернуть расстояние, иначе проверить четырёх соседей: если сосед не выходит за границы и не является стеной, то записать расстояние и добавить соседа в очередь, независимо от того, посещён ли он.
- Извлечь клетку из очереди, если это финиш — вернуть расстояние, иначе проверить четырёх соседей: если сосед не выходит за границы, не является стеной и ещё не посещён, то записать расстояние (dist[текущая] + 1) и добавить соседа в очередь.
- Извлечь клетку из очереди, если это финиш — вернуть расстояние, иначе проверить всех соседей: если сосед не выходит за границы, не является стеной и уже посещён, то записать расстояние и добавить соседа в очередь.
- Извлечь клетку из стека, если это финиш — вернуть расстояние, иначе проверить всех соседей: если сосед не выходит за границы, то записать расстояние и добавить соседа в стек.
Ответ и объяснение
Извлечь клетку из очереди, если это финиш — вернуть расстояние, иначе проверить четырёх соседей: если сосед не выходит за границы, не является стеной и ещё не посещён, то записать расстояние (dist[текущая] + 1) и добавить соседа в очередь.
Правильный вариант: извлечь клетку из очереди, если это финиш — вернуть расстояние, иначе проверить четырёх соседей: если сосед не выходит за границы, не является стеной и ещё не посещён, то записать расстояние (dist[текущая] + 1) и добавить соседа в очередь. Остальные варианты неверны: BFS использует очередь, а не стек; проверка на посещённость обязательна; если клетка уже посещена, её не нужно добавлять снова.
Почему клетку нужно помечать как посещённую сразу при добавлении в очередь, а не при извлечении?
- Если помечать при извлечении, алгоритм будет работать быстрее, так как не нужно проверять посещённость при добавлении.
- Нет разницы, когда помечать клетку, это не влияет на работу алгоритма.
- Если помечать при добавлении, алгоритм может пропустить некоторые клетки, поэтому лучше помечать при извлечении.
- Если помечать при извлечении, одна и та же клетка может быть добавлена в очередь много раз, что замедлит алгоритм. При немедленной отметке клетка попадает в очередь ровно один раз.
Ответ и объяснение
Если помечать при извлечении, одна и та же клетка может быть добавлена в очередь много раз, что замедлит алгоритм. При немедленной отметке клетка попадает в очередь ровно один раз.
Правильный вариант: если помечать при извлечении, одна и та же клетка может быть добавлена в очередь много раз, что замедлит алгоритм. При немедленной отметке клетка попадает в очередь ровно один раз. Остальные варианты неверны: немедленная отметка не замедляет, а ускоряет; она не пропускает клетки; разница есть и существенна.
Чем отличается нерекурсивный BFS от нерекурсивного DFS?
- BFS использует очередь, а DFS — стек. В остальном код практически одинаков.
- BFS использует стек, а DFS — очередь. В остальном код практически одинаков.
- BFS обрабатывает клетки в глубину, а DFS — в ширину.
- BFS использует рекурсию, а DFS — итеративный подход.
Ответ и объяснение
BFS использует очередь, а DFS — стек. В остальном код практически одинаков.
Правильный вариант: BFS использует очередь, а DFS — стек. В остальном код практически одинаков. Остальные варианты неверны: BFS использует очередь, а не стек; оба алгоритма обычно реализуются итеративно; BFS обрабатывает в ширину, а DFS — в глубину.
Какова временная сложность BFS для матрицы размером N x M?
- O(N^2*M^2), так как BFS может повторно обрабатывать клетки.
- O(N*M), так как инициализация массива dist занимает O(N*M), а обход каждой клетки — ещё O(N*M), итого O(N*M) после отбрасывания констант.
- O(N+M), так как BFS проходит только по границам матрицы.
- O(N*M*4), так как для каждой клетки проверяются 4 соседа, и это нельзя упростить.
Ответ и объяснение
O(N*M), так как инициализация массива dist занимает O(N*M), а обход каждой клетки — ещё O(N*M), итого O(N*M) после отбрасывания констант.
Правильный вариант: O(N*M), так как инициализация массива dist занимает O(N*M), а обход каждой клетки — ещё O(N*M), итого O(N*M) после отбрасывания констант. Остальные варианты неверны: BFS обходит все клетки, а не только границы; константа 4 отбрасывается; каждая клетка обрабатывается ровно один раз.
Какова оценка памяти BFS для матрицы N x M?
- O(N+M), так как очередь никогда не превышает сумму размерностей.
- O(N*M*2), так как и массив dist, и очередь занимают по N*M, и константу 2 нельзя отбросить.
- O(N*M), так как массив dist занимает O(N*M), а очередь в худшем случае (например, H-фрактал) может вырасти до O(N*M), итого O(N*M) после отбрасывания констант.
- O(1), так как BFS не требует дополнительной памяти.
Ответ и объяснение
O(N*M), так как массив dist занимает O(N*M), а очередь в худшем случае (например, H-фрактал) может вырасти до O(N*M), итого O(N*M) после отбрасывания констант.
Правильный вариант: O(N*M), так как массив dist занимает O(N*M), а очередь в худшем случае (например, H-фрактал) может вырасти до O(N*M), итого O(N*M) после отбрасывания констант. Остальные варианты неверны: очередь может быть порядка N*M, а не N+M; константа 2 отбрасывается; BFS требует памяти для dist и очереди.
Как восстановить кратчайший путь от финиша до старта после выполнения BFS?
- Использовать стек для хранения всех посещённых клеток и затем извлечь их в обратном порядке
- Идти по цепочке dist от финиша к старту, уменьшая расстояние на 1
- Идти по цепочке prev от финиша к старту, пока не встретится маркер старта
- Повторно запустить BFS от финиша к старту и записать маршрут
Ответ и объяснение
Идти по цепочке prev от финиша к старту, пока не встретится маркер старта
Правильный вариант: после BFS у нас есть словарь prev, где для каждой клетки записана клетка-родитель, из которой мы в неё пришли. Начиная с финиша и переходя к prev[текущая], мы движемся назад, пока не достигнем старта (который имеет prev = -1,-1). Вариант с dist неверен, так как dist хранит расстояние, а не ссылку на родителя. Повторный запуск BFS не нужен и не даст цепочки. Стек с посещёнными клетками не сохраняет информацию о том, откуда пришли.
Почему добавление prev для восстановления пути не меняет асимптотическую оценку времени и памяти BFS?
- Потому что prev хранится в отдельной структуре, которая не учитывается в оценке
- Потому что prev хранит не более N*M записей, а обход и восстановление вместе дают O(N*M) операций
- Потому что восстановление пути выполняется только один раз и не влияет на общую сложность
- Потому что prev заменяет собой массив dist, поэтому общий объём памяти не увеличивается
Ответ и объяснение
Потому что prev хранит не более N*M записей, а обход и восстановление вместе дают O(N*M) операций
Правильный вариант: prev добавляет не более N*M записей, что по памяти O(N*M). Обход BFS занимает O(N*M), восстановление пути — ещё O(N*M), в сумме 2*N*M, что с учётом отбрасывания констант остаётся O(N*M). Вариант про отдельную структуру неверен: все структуры учитываются. Восстановление пути хоть и однократно, но в худшем случае проходит все клетки, поэтому его сложность O(N*M). Prev не заменяет dist, они хранятся параллельно.
В чём ключевая идея Multisource BFS при поиске ближайшей клиники?
- Использовать DFS для обхода от всех клиник одновременно, чтобы найти кратчайший путь
- Запустить BFS из каждой клиники по очереди и выбрать минимальное расстояние до пациента
- Поместить в очередь все клиники и запустить одну волну BFS, сохраняя для каждой клетки ближайшую клинику-источник
- Запустить BFS от пациента, а при встрече клиники запомнить её и продолжить поиск других клиник
Ответ и объяснение
Поместить в очередь все клиники и запустить одну волну BFS, сохраняя для каждой клетки ближайшую клинику-источник
Правильный вариант: Multisource BFS помещает все клиники в очередь как стартовые точки, затем запускает общую волну. Для каждой клетки запоминается, от какой клиники дошли (источник). Когда волна достигает пациента, сразу известно, какая клиника ближайшая. Вариант с последовательным запуском BFS из каждой клиники — это альтернативный, но не Multisource подход. Запуск BFS от пациента и остановка при первой клинике — это другой метод (описан в следующем блоке). DFS не гарантирует кратчайшего пути.
Почему для задачи поиска ближайшей клиники рекомендуется запускать BFS от пациента, а не Multisource BFS?
- Потому что такой код лаконичнее и понятнее, при той же асимптотической сложности O(N*M)
- Потому что BFS от пациента всегда быстрее, чем Multisource BFS
- Потому что Multisource BFS не может найти кратчайший путь до пациента
- Потому что BFS от пациента не требует хранения информации об источнике для каждой клетки
Ответ и объяснение
Потому что такой код лаконичнее и понятнее, при той же асимптотической сложности O(N*M)
Правильный вариант: в материале указано, что запуск BFS от пациента до первой встреченной клиники — более простое и лаконичное решение, при этом оценка по времени и памяти остаётся O(N*M) для обоих вариантов. Вариант про скорость неверен: асимптотически оба решения одинаковы. Multisource BFS как раз находит кратчайший путь. BFS от пациента всё равно хранит dist и prev, поэтому память не меньше.
Какие задачи, по материалу, оптимально решает DFS?
- Все перечисленные задачи, включая поиск кратчайшего пути
- Подсчёт компонент связности и задачу со скорой помощью
- Заливку и проверку существования пути
- Поиск кратчайшего расстояния и восстановление маршрута
Ответ и объяснение
Заливку и проверку существования пути
В источнике сказано, что DFS оптимально решает только две первые задачи: заливку и проверку существования пути. Поиск кратчайшего расстояния, восстановление маршрута и задача со скорой помощью решаются BFS, а не DFS.
Почему BFS считается более универсальным для собеседований?
- BFS решает все рассмотренные задачи: заливку, проверку пути, кратчайшее расстояние, восстановление маршрута и задачу со скорой помощью
- BFS работает только на матрицах, а DFS — на любых графах
- BFS всегда требует меньше памяти, чем DFS, поэтому его проще реализовать
- BFS не требует пометки посещённых клеток, что упрощает код
Ответ и объяснение
BFS решает все рассмотренные задачи: заливку, проверку пути, кратчайшее расстояние, восстановление маршрута и задачу со скорой помощью
В материале подчёркивается, что BFS решает все перечисленные задачи, включая поиск кратчайшего расстояния и восстановление маршрута, тогда как DFS оптимален лишь для заливки и проверки существования пути. Остальные варианты не соответствуют источнику: BFS не всегда экономичнее по памяти, пометка посещённых клеток нужна и в BFS, а ограничение BFS только матрицами не упоминается.
Почему кандидаты часто выбирают рекурсивный DFS при решении задач на графы?
- Он проще всего запоминается и требует всего 5–10 строк кода
- Он всегда даёт оптимальное решение для поиска кратчайшего пути
- Он расходует память более контролируемо, чем BFS
- Он гарантирует отсутствие переполнения стека при больших входных данных
Ответ и объяснение
Он проще всего запоминается и требует всего 5–10 строк кода
В источнике указано, что рекурсивный DFS проще всего запомнить: 5–10 строчек кода и решение готово. Переполнение стека как раз является риском рекурсивного DFS, кратчайший путь он не ищет, а контролируемый расход памяти характерен для BFS.
Какой риск сохраняется при замене рекурсивного DFS на нерекурсивный?
- Вероятность пика потребления памяти остаётся высокой
- Алгоритм перестаёт находить компоненты связности
- Время работы возрастает с O(N*M) до O(N^2*M)
- Появляется риск переполнения стека вызовов
Ответ и объяснение
Вероятность пика потребления памяти остаётся высокой
В материале сказано, что нерекурсивный DFS избавляет от переполнения стека, но вероятность пика потребления памяти в N остаётся всё ещё высокой. Переполнение стека вызовов — проблема рекурсивной версии, а изменения сложности и способности находить компоненты связности не упоминаются.
Почему BFS считается безопаснее по памяти, чем DFS?
- BFS хранит только одну ветку пути, как и рекурсивный DFS
- Память расходуется более контролируемо, и худшие случаи встречаются редко
- BFS не требует хранения посещённых клеток
- BFS вообще не использует дополнительную память
Ответ и объяснение
Память расходуется более контролируемо, и худшие случаи встречаются редко
Источник утверждает, что BFS безопаснее: память расходуется более контролируемо, и худшие случаи встречаются редко. BFS не может обходиться без дополнительной памяти, не хранит только одну ветку и требует отметок посещения.
Как выбор реализации обхода связан с опытом интервьюера?
- Опытный интервьюер всегда требует рекурсивный DFS, а менее опытный — BFS
- Опытный интервьюер запрещает использовать BFS из-за сложности
- Опытный интервьюер чаще предлагает BFS, а менее опытный — рекурсивный DFS
- Выбор реализации не зависит от опыта интервьюера
Ответ и объяснение
Опытный интервьюер чаще предлагает BFS, а менее опытный — рекурсивный DFS
В материале говорится: если интервьюер разбирается в графах, он почти всегда говорит давай BFS; более зелёный обычно отвечает давай не усложнять, напишем DFS. Остальные варианты противоречат источнику.