hottabxp
@hottabxp
Миллиардер. Честно, 100 пистонов!

Какой алгоритм используется в пакетных менеджерах?

Пилю свой менеджер пакетов на Python(аналог apt). Переконвертировал файлы "Packages" в базу SQLite.
Теперь не могу понять, как работать с зависимостями. Например: есть пакеты A,B,C,D,E...:
Нужно скачать пакет D со всеми зависимостями.
Пакет D зависит от B;
Пакет B зависит от A и C;
Пакет C зависит от B;
Можете объяснить простыми словами алгоритм, который используется в APT? Когда-то даже находил названия алгоритма, сейчас не могу найти.
  • Вопрос задан
  • 75 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Это называется топологическая сортировка. Реализуется обычно одним поиском в глубину. Есть статья на хабре.

Можно построить нужный вам порядок только для ациклических графов (без циклов).

Обычно, реализация алгоритма заодно и найдет хотябы один цикл, если граф не ацикличен. Надо только написать сообщение об ошибке в нужном месте.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@Mercury13
Программист на «си с крестами» и не только
Циклических зависимостей (B → C → B) обычно не бывает. Но вам нужен самый тупой поиск — например, в глубину.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы