Сортировка по зависимостям
Есть список объектов, у них есть поле, в котором указаны зависимости
class A:
dependencies = []
class B:
dependencies = []
class C:
dependencies = [A]
class D:
dependencies = [B]
class E:
dependencies = [A, B, C]
class F:
dependencies = [E]
class G:
dependencies = [F]
Изначально весь набор объектов валиден, все объекты в зависимостях имеются, нет цикличности.
Как отсортировать произвольный набор объектов по зависимостям?
Порядок должен быть такой: 1 Объект встает в список если все зависимости уже добавлены 2 Если нет какой либо зависимости, ждем пока она появится 3 Если не осталось объектов с полными зависимостями, то добавляем обхекты независимые от уже добавленных 4 см п 1 (по кругу) пока изначальный список не будет полностью в новом
Подскажите алгоритм?
Примеры входных/выходных данных
> [A, C, E, B, D]
< [A, B, C, D, E] или [A, B, D, C, E]
> [B, E, A, D, G, F]
< [B, A, D, E, F, G]
Предполагаю, сначала надо пройтись по объектам и записать, какие объекты зависят от них, и смотреть исходя из этих данных