Обход структуры данных

Question

Допустим, у меня есть пакет A версия 1 и пакет A версия 2 , Назову их A1 и A2 соответственно.

Если у меня есть пул пакетов: A1 , A2 , B1 , B2 , C1 , C2 , D1 , D2

A1 зависит от B1 , будет обозначаться как (A1, (B1)).

Plus A1 зависит от любой версии пакета C" C1 или C2 удовлетворяет A1", будет представлять собой (A1, (C1, C2))

, объединяющих A1 deps вместе, затем A1 структура данных становится: (A1, (B1), (C1, C2))

Также B1 зависит от D1 : (B1, (D1))

A1 структура становится: (A1, ((B1, (D1))), (C1, C2))

аналогично A2 структура (A2, ((B2, (D2))), (C1, C2))

Мой вопрос таков: как выбрать лучшего кандидата пакета A где я могу выбрать на основе условия (дляНапример, условие заключается в том, что пакет не конфликтует с текущими установленными пакетами.)

путем объединения A1 и A2 : ((A1, ((B1, (D1))), (C1, C2)), (A2, ((B2, (D2))), (C1, C2)))

Howмогу ли я пройти эту структуру данных

Так что начните с A1 , если не конфликтует проверка B1 , если не конфликтует проверка D1 , если нет конфликта, проверьте ( C1 , C2 ) и выберите один из них: C1 или C2 .После этого я выбираю (A1, B1, D1, C1).

В случае, если A1 или какой-либо из его операций не соответствует условию (например, если B1 конфликтует сустановленных пакетов), затем полностью удалите A1 и перейдите к проверке A2 .затем заканчивайте с (A2, B2, D2, C1).

Что это за обход?

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

Answer 1

Вы можете использовать список смежности для представления данных: Предположим, пакеты: A1, A2, B1, B2, C1, C2.И A1 зависит от B1 и C2, A2 зависит от B1 и C1 и C2.Приведенные выше данные могут быть представлены как

[A1] -> [B1, C2]
[A2] -> [B1, C1, C2]

. Использовать Топологическая сортировка , чтобы получить порядок зависимостей

.

Answer 2

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

1. Обратите внимание, что порядок толькоприменимо к бинарным деревьям.У любого другого вида дерева нет обхода в порядке.Если ваша общая проблема имеет B1, B2, B3, то, очевидно, не было бы двоичного представления дерева.

2. Одно свойство прохождения - это то, что деревоимеет всю информацию включительно в себе.Когда вы пересекаете дерево, вы никогда не беспокоитесь о «внешней информации».В вашем случае ваше дерево не является полным в информации - вам нужно зависеть от внешней информации, чтобы увидеть, есть ли конфликт.например, установлен B1 - эта информация никогда не отображается в дереве.