Может ли быть несколько родителей И несколько корней для направленного ациклического графа?

Question

Может ли быть несколько родителей и / или несколько корней для DAG?

Answer 1

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

Answer 2

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

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

Источник: Википедия

Как минимум, направленный ациклический граф должен иметь:

• Узлы: место для хранения данных.
• Направленные края: стрелки, указывающие в одном направлении (то, что отличает эту структуру данных)
• Какой-то великий наследственный узел без родителей. (Интересный факт: большинство деревьев предков на самом деле являются группами DAG, а не деревьями, потому что кузены в какой-то момент вступают в брак друг с другом.)
• Листья: Узлы без детей