Вы работаете над поиском авиабилетов для Яндекс Путешествий. Пользователи часто хотят летать между городами, которые могут не иметь прямого авиасообщения. Ваша задача — реализовать функцию findPath, которая будет строить маршрут между двумя городами.
Формат ввода. Вы получаете на вход 3 аргумента:
from — откуда летим (код аэропорта);
to — куда летим (код аэропорта);
fetchFlights(from) — функция, которая возвращает список кодов аэропортов, до которых можно долететь напрямую из from.
Сеть маршрутов представляет собой дерево (граф без циклов), где в каждый аэропорт ведёт не более одного прямого рейса.
Формат вывода. Верните массив кодов аэропортов, представляющий полный маршрут от from до to включительно. Если такого маршрута не существует, необходимо вернуть пустой массив.
/** * Временная сложность: O(V + E) * Алгоритмически это поиск в ширину (BFS). Мы посещаем каждый узел (V) * один раз и проходим по каждому ребру (E) один раз. * (Технически в JS array.shift() работает за O(V), что может ухудшить время, * но для оценки алгоритма обычно считается, что очередь работает за O(1)). * * Пространственная сложность: O(V) * Память расходуется линейно: храним словарь родителей (parent), * множество посещенных (visited) и очередь, размер которых не превышает V. */async function findPath(from, to, fetchFlights) { if (from === to) { return [from]; } // Space: O(V) — очередь в худшем случае хранит слой графа const queue = [from]; // Space: O(V) — храним ссылку на родителя для каждого узла const parent = new Map([[from, null]]); // Space: O(V) — множество для отслеживания уникальных узлов const visited = new Set([from]); // Time: Внешний цикл выполняется V раз (по количеству узлов) while (queue.length > 0) { // Time: O(V) для массива (сдвиг), O(1) если использовать правильную структуру Queue const current = queue.shift(); const destinations = await fetchFlights(current); if (!destinations) { continue; } // Time: Суммарно этот цикл по всем вызовам выполнится E раз (общее кол-во ребер) for (const destination of destinations) { if (visited.has(destination)) { continue; } visited.add(destination); parent.set(destination, current); if (destination === to) { // Time: O(V) — восстановление пути длиной до V return buildPath(parent, to); } queue.push(destination); } } return [];}function buildPath(parent, to) { const path = []; let current = to; // Time: O(V) — проход обратно по цепочке родителей while (current !== null) { path.push(current); current = parent.get(current); } // Time: O(V) — переворот массива return path.reverse();}
Альтернативное решение (BFS с хранением пути в очереди)
/** * Временная сложность: O(V * E) * В худшем случае мы проходим по всем ребрам (E), и на каждой итерации * копируем массив пути длиной до V. (Также queue.shift добавляет O(V^2)). * * Пространственная сложность: O(V^2) * В очереди одновременно может находиться O(V) узлов, и для каждого * мы храним отдельный массив пути длиной до O(V). */async function findPath(from, to, fetchFlights) { if (from === to) { return [from]; } // Space: O(V) — начальная инициализация const queue = [[from, [from]]]; const visited = new Set([from]); while (queue.length > 0) { // Time: O(V) — удаление первого элемента из массива (сдвиг всех остальных) // Space: O(V) — извлечение ссылки на массив пути const [current, pathToCurrent] = queue.shift(); const destinations = await fetchFlights(current); if (!destinations) { continue; } // Time: Этот цикл выполняется для всех ребер в графе (всего E раз) for (const destination of destinations) { if (destination === to) { // Time: O(V) — копирование итогового пути return [...pathToCurrent, destination]; } if (!visited.has(destination)) { visited.add(destination); // Time: O(V) — Spread operator [...] копирует весь текущий путь. // Поскольку это происходит внутри цикла по ребрам, общая сложность растет до O(E * V). // Space: O(V) — создается новый массив пути для каждого соседа. // В сумме в очереди это займет O(V^2) памяти. queue.push([destination, [...pathToCurrent, destination]]); } } } return [];}
Альтернативное решение (DFS рекурсивный)
/** * Временная сложность: O(V^2 + E) * Стандартный DFS работает за O(V + E), но из-за оператора spread [...path] * внутри рекурсии мы тратим O(V) на копирование данных на каждом шаге. * * Пространственная сложность: O(V^2) * В худшем случае (длинная цепочка) стек рекурсии достигает глубины V. * Поскольку на каждом уровне хранится своя копия массива пути, * суммарное потребление памяти растет квадратично. */async function findPath(from, to, fetchFlights) { // Space: O(V) — хранит посещенные узлы const visited = new Set(); async function dfs(current, path) { if (current === to) { // Time: O(V) — копирование итогового пути return [...path, current]; } visited.add(current); const destinations = await fetchFlights(current); if (!destinations) { return null; } // Time: Суммарно цикл проходит по всем ребрам (E) for (const destination of destinations) { if (!visited.has(destination)) { // Time: O(V) — самая "тяжелая" операция. Копирование массива path // происходит при каждом спуске вглубь. // Space: O(V) — создание нового массива для следующего кадра стека. // При глубине V это приводит к O(V^2) общей памяти в стеке. const result = await dfs(destination, [...path, current]); if (result) { return result; } } } } const result = await dfs(from, []); return result ?? [];}
Альтернативное решение (DFS на стеке)
async function findPath(from, to, fetchFlights) { // Space: O(V) — инициализация // В стеке храним состояние, которое раньше передавалось аргументами функции const stack = [{ current: from, path: [] }]; const visited = new Set(); while (stack.length > 0) { // Time: O(1) — pop() с конца массива работает быстро. // Это делает обход поиском в глубину (LIFO - Last In, First Out). const { current, path } = stack.pop(); if (current === to) { // Time: O(V) — формирование финального результата return [...path, current]; } // Если узел уже был обработан через другой путь, пропускаем if (visited.has(current)) { continue; } visited.add(current); const destinations = await fetchFlights(current); if (!destinations) { continue; } // Важно: чтобы порядок обхода был идентичен рекурсии (слева направо), // в стек соседей нужно добавлять в обратном порядке (reverse), // но для обычного DFS порядок соседей обычно не критичен. for (const destination of destinations) { if (!visited.has(destination)) { // Time: O(V) — КОПИРОВАНИЕ ПУТИ. // Мы вручную сохраняем историю для каждого узла в стеке. // Space: O(V) — выделение памяти под новый массив пути для каждого соседа. stack.push({ current: destination, path: [...path, current], }); } } } return [];}