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

Question

[Сергей Карбивничий]

Пилю свой менеджер пакетов на Python(аналог apt). Переконвертировал файлы "Packages" в базу SQLite.
Теперь не могу понять, как работать с зависимостями. Например: есть пакеты A,B,C,D,E...:
Нужно скачать пакет D со всеми зависимостями.
Пакет D зависит от B;
Пакет B зависит от A и C;
Пакет C зависит от B;
Можете объяснить простыми словами алгоритм, который используется в APT? Когда-то даже находил названия алгоритма, сейчас не могу найти.

Comments

[Ромзес Панагиотис]

Работаете вместе?
Как сделать простой менеджер пакетов?

[Сергей Карбивничий]

Ромзес, Нет.

[Ромзес Панагиотис]

Сергей Карбивничий, было интервью с разработчиком cupt
https://sdcast.ksdaemon.ru/2015/03/sdcast-23/
Возможно, будет полезно.

[Сергей Карбивничий]

Ромзес, Спасибо, послушаю на досуге.

Answer 1

[Mercury13]

Циклических зависимостей (B → C → B) обычно не бывает. Но вам нужен самый тупой поиск — например, в глубину.

Comments

[Сергей Карбивничий]

Циклических зависимостей (B → C → B) обычно не бывает.

libgcc1 зависит от gcc-8-base и libc6
libc6 зависит от libgcc1

[Mercury13]

Сергей Карбивничий, Что есть циклы, что их нет — в любом случае надо отмечать всё, что пройдено.

[Сергей Карбивничий]

Mercury13, Благодарю.

Answer 2

[Wataru]

Это называется топологическая сортировка. Реализуется обычно одним поиском в глубину. Есть статья на хабре.

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

Обычно, реализация алгоритма заодно и найдет хотябы один цикл, если граф не ацикличен. Надо только написать сообщение об ошибке в нужном месте.