Упорядочить объекты в иерархических списках в соответствии с их взаимозависимостью

Question

У меня есть несколько объектов с взаимозависимостью.

• B (зависит от A)
• C (зависит от B)
• D
• E (зависит от B и F)
• F (зависит от C)
• г
• H (зависит от B)

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

Предыдущий список объектов будет размещен так:

1. A, D, G (эти объекты не имеют зависимостей)
2. B (B зависит от A)
3. C, H (C и H зависит от B)
4. F (F зависит от C)
5. E (E зависит от B и F)

Какой алгоритм может решить эту проблему?

Answer 1

Если у вас нет вспомогательной структуры, вам следует использовать грубую силу.

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

Итак, в вашем примере у меня будет 5 узлов в вертикальном списке, а для первого узла у меня будет список из 3 узлов (первый узел будет содержать A, второй D и третий G). Второй узел вертикального списка будет иметь список с одним узлом, который будет содержать B и так далее.

Таким образом, алгоритм будет выглядеть примерно так:

1.For every item
2.  if item.dependency in list
3.    append item in the correct node
4.  else // item not in list
5.    create node in list with the dependency of the item
6.    append item in the created node

Итак, в приведенном выше псевдокоде, когда я говорю "список", я имею в виду вертикальный код.

На шаге 1 мы проверяем все предметы, которые у вас есть.

На шаге 2 вы проверяете, существует ли элемент, который вы сейчас обрабатываете, в списке (просматривая весь список и возвращая найденную позицию или что-то более умное).

На шаге 3 вы переходите в позицию, найденную на шаге 2, и вставляете в конец списка, расположенного в узле, положение позиции вашего элемента (вам не нужно снова сохранять зависимость). Обратите внимание, что если узел в позиции не имеет записей в своем списке, то вам также необходимо создать его список.

На шаге 4 мы имеем дело с тем, что наш элемент не найден в списке.

На шаге 5 мы создаем новый узел в списке, который будет иметь в качестве значения зависимость элемента.

На шаге 6 мы вставляем элемент в узел, созданный на шаге 5.

Надеюсь это поможет!