LatornLatorn
Войти

SQL: Обход графа и защита от циклов — Простые маршруты и допустимые продолжения

Практическая задача по SQL на тему «Обход графа и защита от циклов». В условии приведены схема таблиц, ограничения данных, имена столбцов результата и порядок сортировки. Напишите один SELECT или WITH-запрос для SQLite. Перед проверкой продумайте пустой результат, повторяющиеся строки и границы диапазонов, если они встречаются в условии. Проверяется результат запроса, поэтому допустима эквивалентная реализация. Сначала решите задачу самостоятельно; продолжение практики доступно в полном курсе продвинутого SQL.

Простые маршруты и допустимые продолжения

Что уже дано

Таблица routes(source_id INTEGER NOT NULL, target_id INTEGER NOT NULL, PRIMARY KEY(source_id,target_id)) хранит ориентированные рёбра. Не более 8 различных узлов; ID — положительные целые до 1000000. Циклы и самопетли допустимы, одинаковые рёбра не повторяются. Отдельной таблицы узлов нет; исходный узел1 считается существующим даже без рёбер.

Что нужно сделать

Верните все простые пути из узла1, включая исходный путь длины0. Простой путь не посещает один и тот же узел дважды. node_id — последний узел, depth — число рёбер, path — все ID в порядке посещения через /, с / в начале и конце. Разные пути к одному узлу остаются отдельными строками. next_choices — число исходящих рёбер из текущего узла, которые можно добавить к этому конкретному пути без повторного посещения узла. Самопетля и возврат к любому уже посещённому ID не являются допустимым продолжением.

Ввод и вывод

Отправьте один SELECT или WITH-запрос; stdin и печать не используются. Ровно 4 столбцов в указанном порядке и с этими именами: node_id, depth, path, next_choices. node_id, depth и next_choices — INTEGER; path — TEXT; NULL нет. Сортировка: depth ASC, node_id ASC, path ASC COLLATE BINARY. При пустой routes верните (1,0,/1/,0). В тестовых результатах разделитель |, NULL — пустое поле. Допускается любой эквивалентный запрос.

Пример

Подготовка данных
INSERT INTO routes VALUES (1,25),(25,5),(5,1),(25,25),(1,2),(2,3),(3,4);
Вывод
1|0|/1/|2
2|1|/1/2/|1
25|1|/1/25/|1
3|2|/1/2/3/|1
5|2|/1/25/5/|0
4|3|/1/2/3/4/|0
РешениеSQL · SQLite

Без регистрации. Гостевая проверка не сохраняет прогресс. Для сохранения перейдите к уроку.

Отправьте решение, чтобы увидеть результаты тестов.

Связанные задачи