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

Question

В нашем скрипте сборки мы разделяем наши приложения на компоненты.

Сценарий будет таким.

Любой компонент может зависеть от одного или нескольких компонентов.

Например У нас есть компоненты от 1 до 12.

Компонент1 зависит от компонента2 и компонента3.

Компонент 4 зависит от компонента2 и компонента6

Если в сценарии я укажу компоновку component1 и component4 с зависимостями, тогда он должен быть собран в следующем порядке: Component2, component3, component1, component6 и component4.

Какой алгоритм будет полезен для нахождения зависимости и обеспечения того, чтобы ни один компонент не выполнялся дважды.

Answer 1

Вы можете построить граф зависимостей, а затем использовать топологическую сортировку , чтобы определить порядок компиляции.

Answer 2

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

Редактировать: Не содержит кофеина.Используйте топологическую сортировку, как было предложено.Мое решение может или не может работать.