Псевдокод для получения заказа на основе зависимостей

Question

Хорошо, это моя ситуация. У меня есть список предметов, и мне нужно получить заказ этих предметов на основе их ссылок. Например позволяет сказать, что у нас есть эти пункты: A, B, C, D, E, F

C и D не имеют зависимостей, поэтому их порядок может быть 0. B является тот, который имеет самое с C, D и А. а имеет С и Р имеет а и В

C D  
    | \/
    A/
/|/
| B 
\ | 
    F 

В этом случае C, D = 0 а = 1 В = 2 F = 3

Я был глядя через Интернет, и кажется, что я не использую правильный научный термин для этого. Скорее всего, это набор или сумка. Я знаю, что это не дерево, так как эта ситуация имеет более двух ребер на каждом узле. Ответ может быть написан на языке программирования, просто пытаясь сделать его максимально общим.

Answer 1

Простой алгоритм заключается в следующем.

Истерируйте коллекцию, ища элементы, которые не имеют зависимостей: помните эти элементы как «элементы уровня 0».

Итерировать коллекцию снова, ища элементы, которые могут зависеть от «элементов уровня 0», но не от других элементов: помните эти элементы как «элементы уровня 1».

Повторите сборку, ища элементы, которые могут зависеть от «элементов уровня 0» и/или от «элементов уровня 1», но не от других элементов: помните эти элементы как «элементы уровня 2».

Etc.

Stop, когда каждый элемент имеет назначенный уровень.

Answer 2

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