У меня есть список элементов (синие узлы ниже), которые классифицированы пользователями моего приложения. Сами категории могут быть сгруппированы и классифицированы сами.

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

Пример:

(источник:theuprightape.net)

На этой структуре я хочу выполнить следующие операции:

найти все предметы (раковины) ниже определенного узла (все предметы в Европе)найти все пути (если есть), которые проходят через весь набор из n узлов (все элементы, отправленные по SMTP с сайта example.com)найти все узлы, которые лежат ниже всего множества узлов (пересечение: гойская коричневая пища)

Первый кажется довольно простым: начните с узла, следуйте всем возможным путям вниз и соберите элементы там. Однако есть ли более быстрый подход? Запоминание уже пройденных узлов, вероятно, помогает избежать ненужного повторения, но есть ли еще оптимизации?

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

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