У меня есть список элементов (синие узлы ниже), которые классифицируются пользователями моего приложения. Сами категории могут быть сгруппированы и классифицированы.
Полученная структура может быть представлена в виде Directed Acyclic Graph (DAG), где элементы являются поглотителями в нижней части топологии графа и Главными категориями являются источники. Обратите внимание, что, хотя некоторые из категорий могут быть четко определены, многое будет определяться пользователем и может быть очень грязным.
Пример:
примеры данных http://theuprightape.net/dag.png
В этой структуре я хочу выполнить следующие операции:
- найдите все предметы (раковины) под определенным node (все предметы в Европе)
- найти все пути (если они есть), которые проходят через весь набор из n узлов (все элементы, отправленные через SMTP из example.com)
- найдите все узлы, которые лежат ниже всего набора узлов (пересечение: говядино-коричневые продукты).
Первое кажется довольно простым: начинайте с node, следуйте по всем возможным путям вниз и собирайте там предметы. Однако существует ли более быстрый подход? Помните, что узлы, которые я уже прошел, вероятно, помогают избежать ненужного повторения, но есть ли больше оптимизаций?
Как мне перейти ко второму? Похоже, что первым шагом было бы определить высоту каждого node в наборе, чтобы определить, на каком этапе (-ых) начать, а затем найти все пути ниже того, что включает в себя остальную часть набора. Но является ли это лучшим (или даже хорошим) подходом?
алгоритмы обхода графика, перечисленные в Википедии, все, похоже, связаны с поиском конкретного node или самого короткого или наиболее эффективного маршрута между двумя узлами. Я думаю, что это не то, что я хочу, или я просто не понимаю, как это относится к моей проблеме? Где еще мне читать?
