Код Senior Графы: BFS и DFS обновлено
Топологическая сортировка
Условие
Верни порядок вершин, при котором каждое ребро идёт слева направо. Граф - список смежности. Если порядок невозможен, верни пустой массив. При равных вариантах бери вершины в порядке ключей объекта.
Примеры
topoSort({"a":["b"],"b":["c"],"c":[]}) // ["a", "b", "c"]
topoSort({"a":["c"],"b":["c"],"c":[]}) // ["a", "b", "c"]
topoSort({"a":["b"],"b":["a"]}) // []
Как подойти
Алгоритм Кана: очередь вершин с нулевой входящей степенью. Сравнение длины результата с числом вершин - бесплатная проверка на цикл. Практическая аналогия - порядок сборки модулей или выполнения задач с зависимостями.
Подсказки: 3
- Считай, сколько рёбер входит в каждую вершину.
- Начинай с вершин без входящих рёбер и снимай рёбра по мере обработки.
- Если обработали не все вершины - в графе цикл.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.