подмножество топологических подмножеств узлов в графе

Question

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

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

Есть ли лучший способ сделать это или известный алгоритм поиска топологического типа подмножества узлов?

Answer 1

Оптимальным решением может быть построение нового графика только узлов, выбранных пользователем, с соответствующими зависимостями. Например, если A -> B -> C, пользователь выбирает A и C, ваш построенный граф A -> C. Затем выполните стандартную топологическую сортировку.