Как отсортировать зависимые объекты по зависимости

У меня есть коллекция:

List> dependencyHierarchy;

Первый элемент в паре - это какой-то объект (элемент) и второй - это набор объектов того же типа, от которых зависит первый. Я хочу получить список List в порядке зависимости, поэтому нет элементов, которые зависят от первого элемента и т. д. (без циклической зависимости!).

Ввод:

Item4 depends on Item3 and Item5
Item3 depends on Item1
Item1 does not depend on any one
Item2 depends on Item4 
Item5 does not depend on any one 

Результат:

Item1
Item5
Item3
Item4
Item2

Спасибо.

РЕШЕНИЕ:

Топологическая сортировка (спасибо Loïc Février за идею)

и

пример на C # , пример на Java (спасибо xcud за отличные примеры )

72
задан Community 23 May 2017 в 10:31
поделиться