Как изменить алгоритм обхода дерева предзаказа для обработки узлов с несколькими родителями?

Question

Я долго искал и не могу найти альтернативного решения. Мне нужен алгоритм обхода дерева таким образом, чтобы узел мог иметь более 1 родителя, если это возможно (найдена отличная статья здесь: Хранение иерархических данных в базе данных ). Существуют ли какие-либо алгоритмы, чтобы, начиная с корневого узла, мы могли определить последовательность и зависимости узлов (в настоящее время читая топологическую сортировку)?

Answer 1

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

Типичные алгоритмы обхода для графиков: в глубину и в ширину . Реализация графа отличается только тем, что записывает уже посещенные узлы, чтобы избежать посещения определенных узлов несколько раз. Однако, если ваша структура данных гарантирует, что она ациклична, вы можете использовать древовидные алгоритмы на вашем графе, просто рассматривая «родителей» как «детей».

Я сделал простой набросок, чтобы проиллюстрировать, что я имею в виду (отличный шанс попробовать новую функцию рисования в Документах Google):

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

Answer 2

Дерево - это в основном ориентированный невзвешенный граф, в котором каждая вершина имеет N или меньше ребер, и циклов не может быть.
Если вы уверены, что в вашем дереве нет циклов, вы можете просто считать родителя другим дочерним узлом указанного узла и нормально выполнить предварительный обход.
Однако, если циклы могут произойти, вам нужны графовые алгоритмы.
В частности: Поиск в ширину .

Answer 3

Вы не описываете дерево здесь. Вы можете НЕ назвать свой график деревом.

Дерево - это ненаправленный граф без циклов. Родительско-дочерние отношения НЕ - это интерпретация направлений, нарисованных по краям. Они являются результатом присвоения одной вершине корня .

Мы называем вершину "родительской" для текущей, потому что она следующая за путем к корню. Все остальные вершины, смежные с текущей, являются "дочерними".

Вы не можете просто разложить произвольный граф таким образом, чтобы «родители» были «выше» или «указывают на вершину», а дети были «ниже» или «точки вершин к ним». Дерево - это дерево, потому что выбран корень. То, что вы изображаете в своем вопросе, не является деревом. А алгоритмы обхода дерева НЕ применимы для обхода произвольных графов.

Существует несколько алгоритмов обхода графа, таких как поиск в ширину или поиск в глубину (см. Дополнительные примечания на этих страницах). Используйте их вместо попыток связать свой полнофункциональный график с вашими знаниями о деревьях.

Answer 4

Просто проверяю, может быть, простой случай: могут ли два родителя иметь разных родителей? Если нет, вы можете превратить их в один узел (концептуально) и снова получить дерево.

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

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

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