logo标签列表

有多个父节点和多个根节点的有向无环图是否存在？

data-structuresdirected-acyclic-graphsoperations-research
3
DAG 是否可以有多个根和/或多个父节点？
2个回答
2

在有向无环图中，没有任何限制阻止一个节点拥有多个父节点。同样地，在有向无环图中也可以存在多个根节点。因此，是的，你可以在有向无环图中拥有这两个特性。

1

DAG 是一个单向流动的图形，其中没有任何元素可以是自己的子节点。但是对于图形的单个节点仍然可以有多个子节点和多个父节点。

enter image description here

一个图由一组顶点和边构成，其中顶点是没有结构的对象，它们通过边成对连接。对于有向图，每个边都有一个方向，从一个顶点指向另一个顶点。在有向图中，路径可以用一系列具有以下性质的边来描述：序列中每条边的结束顶点与序列中下一条边的起始顶点相同；如果第一条边的起始顶点等于最后一条边的结束顶点，则该路径形成一个圆环。有向无环图是指没有圆环的有向图。

来源：维基百科

至少，有向无环图必须具备以下特征：

  • 节点：存储数据的位置。
  • 有向边：只指向一个方向的箭头（这是使该数据结构与众不同的东西）。
  • 某个没有父节点的伟大祖先。（有趣的事实：大多数家谱树实际上是DAG而不是树，因为表亲在某些时候会结婚。）
  • 叶子节点：没有子节点的节点。
所有的家谱树不都是真正的树，因为每个节点都有多个父节点，对吗？ - Calimocho
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接